SDE - 1

1. The problem can be solved using simple recursive traversal.
2. We can keep track of level of a node by passing a parameter to all recursive calls.
3. The idea is to keep track of maximum level also.
4. And traverse the tree in a manner that right subtree is visited before left subtree.
5. Whenever we see a node whose level is more than maximum level so far, we print the node because this is the last node in its level .

The simple idea is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of the maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far.

Initialize:
max_so_far = INT_MIN
max_ending_here = 0

Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
(c) if(max_ending_here < 0)
max_ending_here = 0
return max_so_far

started of with the bruteforce approach to calculate nearest left and nearest right larger height and thereby keep on adding the result.
I then gave a more optimised approach of keeping a left height and right height array and then calculating the result by adding the result for each iteration.

Algorithm:
Create two arrays left and right of size n. create a variable max_ = INT_MIN.
Run one loop from start to end. In each iteration update max_ as max_ = max(max_, arr[i]) and also assign left[i] = max_
Update max_ = INT_MIN.
Run another loop from end to start. In each iteration update max_ as max_ = max(max_, arr[i]) and also assign right[i] = max_
Traverse the array from start to end.
The amount of water that will be stored in this column is min(a,b) – array[i],(where a = left[i] and b = right[i]) add this value to total amount of water stored

1. A naive solution to this problem is to generate all configurations of different pieces and find the highest-priced configuration. This solution is exponential in terms of time complexity.
2. We can get the best price by making a cut at different positions and comparing the values obtained after a cut. We can recursively call the same function for a piece obtained after a cut.
Let cutRod(n) be the required (best possible price) value for a rod of length n. cutRod(n) can be written as follows.
cutRod(n) = max(price[i] + cutRod(n-i-1)) for all i in {0, 1 .. n-1}
Time Complexity: O(n2)

Space Complexity: O(n2)+O(n)
3. I then used an array to store maximum value.
static int cutRod(int price[],int n)
{
int val[] = new int[n+1];
val[0] = 0;

// Build the table val[] in bottom up manner and return
// the last entry from the table
for (int i = 1; i<=n; i++)
{
int max_val = Integer.MIN_VALUE;
for (int j = 0; j < i; j++)
max_val = Math.max(max_val,
price[j] + val[i-j-1]);
val[i] = max_val;
}

return val[n];
}