Formal Problem Statement - You are given array consisting of n integers. Your task is to find the maximum length of an increasing subarray of the given array. A subarray is the sequence of consecutive elements of the array. Subarray is called increasing if each element of this subarray strictly greater than previous. Problem Link - Codeforces - 702A This is a simple problem, with an even simpler solution. We simply transverse across the array comparing each element with the one before it, and maintaining two counters, one for the length of current increasing sequence, and other for the length of overall maxima till this point. Even better, we don't need to store the array, we can transverse by just storing the current, and the element before it. So, the memory required is lesser. After an analysis of this algorithm, we can say that it runs in θ(n) time. #include <iostream> #include <algorithm> using namespace std; int main() { int n, pRead, cRead;
Formal Problem Statement - Find a peak in a 2D array, where a is a 2D-peak iff a ≥ b, a ≥ d, a ≥ c, a ≥ e. If there are more than one peaks, just return one of them. Greedy Ascent Algorithm works on the principle, that it selects a particular element to start with. Then it begins traversing across the array, by selecting the neighbour with higher value. If there is no neighbour with a higher value than the current element, it just returns the current element. Logically, this algorithm is correct, as it returns the element - which has none of it's neighbours greater than the current element. After a bit of thought, we can come to the conclusion that, in a worst case, the whole array will be transversed. Hence, its time complexity is Θ(mn) . Finally, the code using recursion would be, #include <iostream> using namespace std; int a[100][100], n, m; int recur(int i, int j) { if (i > 0 && a[i - 1][j] > a[i][j]) return recur(i - 1,