# DP solution of this problem?

• I know this problem can be easily solved with two pointers with better performance.
But I guess it can be solved with DP too. However, I can't formulate the general equation of DP.
Can anyone give me a hint here?

• The method below might not be the simplest way to do it, but I think it can work. Correct me if there is anything wrong.

L(i) means the max area ends with height(i)

So, L(i)=

``````  L(i-1)
or
(i-x)*Math.min(height[i],height[x])  //the greatest result for all x=0...(i-1)
``````

L(i) should be the bigger one of these two.

• Below is a DP solution. I dont know why its taking long time ?

``````private int max(int a, int b, int c) {
return a > b? a > c ? a : c : b > c? b : c;
}

private int min(int a, int b) {
return a < b ? a : b;
}

private int maxAreaUtil(int[] height, int left, int right, int[][] memo) {

if(left == right) {
return 0;
}
if(memo[left][right] == 0) {
int area = (right-left)*min(height[left], height[right]);
memo[left][right] = area;
}

return max(maxAreaUtil(height, left + 1, right, memo), maxAreaUtil(height, left, right - 1, memo), memo[left][right]);
}

public int maxArea(int[] height) {
int[][] memo = new int[height.length][height.length];
return maxAreaUtil(height, 0, height.length-1, memo);
}
``````

• This method still need O(N^2)..

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.