SDE - 1

This problem can be solved using dynamic programming.
Let A is given array of length n of integers. We define a 2D array las[n][2] such that las[i][0] contains longest alternating subsequence ending at index i and last element is greater than its previous element and las[i][1] contains longest alternating subsequence ending at index i and last element is smaller than its previous element, then we have following recurrence relation between them, 
las[i][0] = Length of the longest alternating subsequence ending at index i and last element is greater than its previous element
las[i][1] = Length of the longest alternating subsequence ending at index i and last element is smaller than its previous element
Recursive Formulation:
las[i][0] = max (las[i][0], las[j][1] + 1); 
for all j < i and A[j] < A[i] 
las[i][1] = max (las[i][1], las[j][0] + 1); 
for all j < i and A[j] > A[i]
Time Complexity: O(n2) 
Auxiliary Space: O(n)

The direct approach to solve this problem is to run two for loops and for every subarray check if it is the maximum sum possible. 
Time complexity: O(N^2), Where N is the size of the array.
Space complexity: O(1)
The efficient approach is to use Kadane's algorithm. It calculates the maximum sum subarray ending at a particular index by using the maximum sum subarray ending at the previous position. 
Steps : 
Declare two variables : currSum which stores maximum sum ending here and maxSum which stores maximum sum so far.
Initialize currSum = 0 and maxSum = INT_MIN.
Now, traverse the array and add the value of the current element to currSum and check : 
1. If currSum > maxSum, update maxSum equals to currSum.
2. If currSum < 0, make currSum equal to zero.
Finally, print the value of maxSum.

Two stacks can be used to implement a min Stack. One stack can be used to store the actual stack elements and the other auxiliary stack is used to store minimum values. The top element of the auxiliary stack will always store the minimum at that point of time. Let us see how push() and pop() operations work.
Push(int x) 
1) push x to the original stack (the stack with actual elements) 
2) compare x with the top element of the auxiliary stack. Let the top element be y. 
…..a) If x < y then push x to the auxiliary stack. 
…..b) If x > y then push y to the auxiliary stack.
int Pop() 
1) pop the top element from the auxiliary stack. This is necessary to update the auxiliary stack. 
2) pop the top element from the original stack and return it.
int getMin() 
1) Return the top element of the auxiliary stack.