# Solve in o(n) JAVA

• 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;
}

}
``````

}

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