bottom up solution works fine ,
but top-down memoized code(JAVA) shows STACKOVERFLOW error,
“Exception in thread “main” java.lang.StackOverflowError”.
Here is my code
public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
class pair
{
int min;
int max;
pair(int a,int b)
{
this.min=a;
this.max=b;
}
}
public pair find(pair dp[],List<Integer> al,int e)
{
if(e==0)
{
dp[0]=new pair(al.get(0),al.get(0));
return (dp[0]);
}
if(dp[e]!=null) return dp[e];
pair p1=find(dp,al,e-1);
int a=al.get(e)*p1.max;
int b=al.get(e)*p1.min;
int c=al.get(e);
int t1=Math.max(a,Math.max(b,c));
int t2=Math.min(a,Math.min(b,c));
dp[e]=new pair(t2,t1);
return dp[e];
}
public int maxProduct(final List<Integer> al) {
pair dp[]=new pair[al.size()];
pair t1= find(dp,al,al.size()-1);
//System.out.println(t1.max);
int mm=Integer.MIN_VALUE;
for(int i=0;i<dp.length;i++)
{
//System.out.println(dp[i].max);
mm=Math.max(mm,dp[i].max);
}
return mm;
}
}