Solve in o(n) JAVA


  • 0
    A

    import java.util.*;
    public class Solution {

    public int maxProfit(int[] prices) {
        
        if(prices==null || prices.length<2)return 0;
        
        int[] tmp0 = new int[]{0,0};
        
        findMaxPro(prices,tmp0,0,prices.length);
        
        int price1 = prices[tmp0[1]]-prices[tmp0[0]];
        int price2 = 0;
        
        if(price1>0){
            
            int[] tmp1 = new int[]{0,0};
            int[] tmp2 = new int[]{0,0};
            int[] tmp3 = new int[]{0,0};
            int minIndex = tmp0[0];
            int maxIndex = tmp0[1];
            
    		
            if(maxIndex-minIndex > 2){
                int[] sec = new int[maxIndex-minIndex-1];
                for(int i = maxIndex-1,j = 0; i >minIndex ; i --,j++){
                    sec[j] = prices[i];
                }
    			findMaxPro(sec,tmp3,0,sec.length);
    			price2 = sec[tmp3[1]]-sec[tmp3[0]];
            }
            
            if(minIndex>1){
                findMaxPro(prices,tmp1,0,minIndex);
                price2 = Math.max(prices[tmp1[1]]-prices[tmp1[0]],price2);
            }
            
            if(prices.length - maxIndex > 2){
                findMaxPro(prices,tmp2,maxIndex+1,prices.length);
                price2 = Math.max(prices[tmp2[1]]-prices[tmp2[0]],price2);
            }
        }
        
        return price1+price2;
        
        
    }
    
    public void findMaxPro(int[] prices,int[] p,int startIndex,int endIndex){
        int maxProfit = 0;
        int min=prices[startIndex];
        int minIndex = startIndex;
        int maxIndex = startIndex;
        int tmpMinIndex = startIndex;
        
        for(int i = startIndex ; i <endIndex;i ++){
            if(prices[i]-min>=maxProfit){
                maxProfit = prices[i]-min;
                maxIndex = i;
                minIndex = tmpMinIndex;
            }
            
            if(prices[i]<min){
                min = prices[i];
                tmpMinIndex = i;
            }
        }
        if(maxIndex>minIndex){
            p[0]=minIndex;
            p[1]=maxIndex;
        }
        
        
        
    }
    

    }


Log in to reply
 

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