SDE - 1

The simulation of approach will make things clear: 

Input : arr[] = {3, 10, 2, 11}
LIS[] = {1, 1, 1, 1} (initially)
Iteration-wise simulation : 

arr[2] > arr[1] {LIS[2] = max(LIS [2], LIS[1]+1)=2}
arr[3] < arr[1] {No change}
arr[3] < arr[2] {No change}
arr[4] > arr[1] {LIS[4] = max(LIS [4], LIS[1]+1)=2}
arr[4] > arr[2] {LIS[4] = max(LIS [4], LIS[2]+1)=3}
arr[4] > arr[3] {LIS[4] = max(LIS [4], LIS[3]+1)=3}

We can avoid recomputation of subproblems by using tabulation

The given problem can be solved by using the Greedy Technique and Binary Search. The monotonicity of the problem can be observed that if all packages can be successfully shipped within D days with capacity K, then definitely they can be shipped with any capacity larger than K. Follow the steps below to solve the problem:

Initialize a variable, say ans as -1 to store the resultant minimum capacity of the boat required.
Initialize two variables, say s and e with the maximum element in the given array and the total sum of the array respectively which denotes the lower and upper bounds of the search space.
Iterate until the value of s is less than or equals to e, and perform the following steps:
Initialize a variable, say mid as (s + e)/2.
Check if it is possible to ship all the packages within D days when the maximum capacity allowed is mid. If found to be true, then update the value of ans to mid and the value of e to (mid – 1).
Otherwise, update the value of s to (mid + 1).
After completing the above steps, print the value of ans as the result.

If the height of bars of the histogram is given then the largest area of the histogram can be found. This way in each row, the largest area of bars of the histogram can be found. To get the largest rectangle full of 1’s, update the next row with the previous row and find the largest area under the histogram, i.e. consider each 1’s as filled squares and 0’s with an empty square and consider each row as the base.

Algorithm :- 

Run a loop to traverse through the rows.
Now If the current row is not the first row then update the row as follows, if matrix[i][j] is not zero then matrix[i][j] = matrix[i-1][j] + matrix[i][j].
Find the maximum rectangular area under the histogram, consider the ith row as heights of bars of a histogram. This can be calculated as given in this article Largest Rectangular Area in a Histogram
Do the previous two steps for all rows and print the maximum area of all the rows.

Approach: In the previous solution, to find the highest bar on the left and right, array traversal is needed, which reduces the efficiency of the solution. To make this efficient, one must pre-compute the highest bar on the left and right of every bar in linear time. Then use these pre-computed values to find the amount of water in every array element.
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
Print the total amount of water stored.

Approach: 

Model the solution using graphs. Initialize indegree and outdegree of every vertex as 0. If A knows B, draw a directed edge from A to B, increase indegree of B and outdegree of A by 1. Construct all possible edges of the graph for every possible pair [i, j]. There are NC2 pairs. If a celebrity is present in the party, there will be one sink node in the graph with outdegree of zero and indegree of N-1. 


Algorithm: 

Create two arrays indegree and outdegree, to store the indegree and outdegree
Run a nested loop, the outer loop from 0 to n and inner loop from 0 to n.
For every pair i, j check if i knows j then increase the outdegree of i and indegree of j
For every pair i, j check if j knows i then increase the outdegree of j and indegree of i
Run a loop from 0 to n and find the id where the indegree is n-1 and outdegree is 0