O(n^2) dp solution got LTE but works fine on local computer


  • 0
    Z

    Here is my java code for iterative version dynamic programming solution. It got a LTE for a descending input {10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,9988,9987,9986,9985,9984,9983,...} but this input works fine for my local mac. below is my code:

      public int maxProfit(int[] prices) {
        // linear time to find all possible points
        //boolean start = true;
        if(prices.length==0){
            return 0;
        }
        List<Integer> days = new ArrayList<Integer>();
        days.add(0);
        for(int i=1;i<prices.length-1;i++){
            if((prices[i]>=prices[i+1]&&prices[i]>=prices[i-1])||(prices[i]<=prices[i+1]&&prices[i]<=prices[i-1])){
                days.add(i);
            }
        }
        if(prices.length!=1){
            days.add(prices.length-1);
        }
        //dp to find four ascending days in days
        int num=2;
        int size = days.size();
    
        int[][] maxprofit= new int[size][num];
        for(int i=0;i<days.size();i++){
            for(int j=0;j<num;j++){
                if(i==0){
                    maxprofit[i][j]=0;
                }
    
                else{
                    int maxp =0;
                    for(int k=0;k<=i;k++){
                        int temp;
                        if(j==0||k==0){
                            temp=prices[days.get(i)]-prices[days.get(k)];
                        }
                        else{
                            temp=maxprofit[k-1][j-1]+prices[days.get(i)]-prices[days.get(k)];
                        }
                        if(temp>maxp){
                            maxp = temp;
                        }
                    }
                    maxprofit[i][j]=Math.max(maxprofit[i-1][j],maxp);
                }
            }
        }
        return maxprofit[days.size()-1][1];
    }
    

    Thank you in advanced!


  • 1
    R

    it can be done in O(n)
    take an array "left" to record maximum profit till day i using only one transaction.
    similarly taken an array "right" to record maximum from i th day to end.
    then max profit with atmost two transactions will be max(left[i] +right[i+1])

    class Solution {
    public:
     int max(int a, int b)
     {
         return a>b?a:b;
     }
        int maxProfit(vector<int> &prices) {
            int n,i;
            n=prices.size();
            int cur_max=0,max_profit=0,max1,sum;
            if(n==0 || n==1)
            return 0;
            
            int *diff=(int *)malloc(sizeof(int)*(n-1));
            int *left=(int *)malloc(sizeof(int)*(n-1));
            int *right=(int *)malloc(sizeof(int)*(n-1));
            for(i=1;i<n;i++)
            {
                diff[i-1]=prices[i]-prices[i-1];
            }
            cur_max=max_profit=left[0]=diff[0];
            for(i=1;i<n-1;i++)
            {
                cur_max=max(cur_max+diff[i],diff[i]);
                max_profit=max(cur_max,max_profit);
                left[i]=max_profit;
                
            }
            cur_max=max_profit=right[n-2]=diff[n-2];
            for(i=n-3;i>=0;i--)
            {
                cur_max=max(cur_max+diff[i],diff[i]);
                max_profit=max(cur_max,max_profit);
                right[i]=max_profit;
                
            }
            max1=right[0];
            for(i=0;i<n-2;i++)
            {
                sum=left[i]+right[i+1];
                if(sum > max1)
                max1=sum;
            }
            
            if(max1<0)
            max1=0;
         return max1;   
        }
    };

  • 0
    A

    here's a java solution in O(4N). basic idea is:
    first find maxprofit as you do for one transaciton( maxprofit Q1). the solution will divide the prices array into 3 sections. 0~min, min~max, max~len-1. for section 1, 3, do the maxprofit Q1. for the section 2, do the maxprofit Q1, but reverse the start and end point, and reduce index in the steps. if section 2 produce two other sections, keep them.
    now the job is the sum up 4 sections with 2 in pairs, find the max then return.

    here's the code:

    public int maxProfit(int[] prices) {
    	if (prices.length <=0)
    		return 0;
        int[] minmax = getMinMaxIndex(0, prices.length-1, prices, true);
        int[] minmax2 = getMinMaxIndex(0, minmax[0], prices, true);
        int[] minmax3 = getMinMaxIndex(minmax[1], prices.length - 1, prices, true);
        int[] minmax4 = getMinMaxIndex(minmax[1], minmax[0], prices, false);
        int maxp1 = prices[minmax[1]] - prices[minmax[0]] + prices[minmax2[1]] - prices[minmax2[0]];
        int maxp2 = prices[minmax[1]] - prices[minmax[0]] + prices[minmax3[1]] - prices[minmax3[0]];
        int maxp3 = prices[minmax[1]] - prices[minmax4[1]] + prices[minmax4[0]] - prices[minmax[0]];
        
        if (maxp1 >= maxp2 && maxp1 >= maxp3)
        	return maxp1;
        else if(maxp2 >= maxp1 && maxp2 >= maxp3)
        	return maxp2;
        else if(maxp3 >= maxp1 && maxp3 >= maxp2)
        	return maxp3;
        else 
        	return maxp1;
        
    }
    
    private int[] getMinMaxIndex(int start, int end, int[] prices, boolean isForward){
    	int minIndex = start;
        int tempMinIndex = start;
        int maxIndex = end;
        int maxProfit = Integer.MIN_VALUE;
        for (int i = start; isForward?i<= end:i>=end; i+=(isForward ? 1: -1)){
        	if (prices[tempMinIndex] > prices[i])
        		tempMinIndex = i;
    
        	if (prices[i] - prices[tempMinIndex] > maxProfit){
        		maxProfit = prices[i] - prices[tempMinIndex];
        		minIndex = tempMinIndex;
        		maxIndex = i;
        	}
        }
        int[] results = {isForward?minIndex:maxIndex, isForward?maxIndex:minIndex};
        
        return results;
    }

Log in to reply
 

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