（1）Best Time to Buy and Sell Stock
测试用例：
这一题，首先使用的是暴力办法，中间做了一些局部优化，但是总体复杂度仍然是O（n2），于是乎，妥妥的Time Limit Exceeded，下面是暴力代码
public int maxProfit(int[] prices){int i,j,max,temp,holda,holdb;
if(prices.length==0 || prices.length==1){return 0;
}
temp = prices[0];
max = prices[1]-prices[0];
for(i=0;i<prices.length-1;i++){ if(prices[i]<temp){temp = prices[i];
for(j=i;j<prices.length;j++){ if(prices[j]-prices[i]>max){max = prices[j]-prices[i];
holda = i;
holdb = j;
}
}
}
}
return max;
}
既然TLE了，于是乎，就去想办法了。
可以得到如果本月买入，下个卖出能够得到的收益，然后股票的最大收益问题就变成了一个已知int数组的最大和子串问题。而这个问题本身有很成熟的解决方案：暴力循环--》O（n2），递归--》O（nlgn），动态规划--》O（n） 都可以解决。
/*复杂度：O（n）：accpt*/
public class Solution { public int maxProfit(int[] prices){int temp = 0;
int max = 0;
int[] det = new int[prices.length];
for(int i=0;i<prices.length-1;i++){det[i] = prices[i+1]-prices[i];
}
for(int i=0;i<det.length;i++){temp = temp + det[i];
if(temp < 0){temp = 0;
}
if(temp > max){max = temp;
}
}
return max;
}
}
本题也可以使用下面一题里面的思路，求出所有波段的profit值，在过程中记录获利最大的一个波段，复杂度同样为O（n）。
（2）Best Time to Buy and Sell Stock II
测试用例：
算法：周期性检查波底和封顶的值，profit=prices[封顶]-price[波底]；直到数组全部元素都结束，注意点主要是边界值不能越界。
/*算法复杂度：O（n）*/
public class Solution { public int maxProfit(int[] prices) {int profit = 0;
int minPos = 0;
int maxPos = 0;
while (maxPos < prices.length-1) {minPos = findMin(prices, maxPos);
maxPos = findMax(prices, minPos);
profit = profit +( prices[maxPos] - prices[minPos]);
}
return profit;
}
public int findMax(int[] prices, int pos) {int i;
for(i=pos;i<prices.length-1 && prices[i+1]>=prices[i];i++){}
return i;
}
public int findMin(int[] prices, int pos) {int i;
for(i=pos;i<prices.length-1 && prices[i+1]<=prices[i];i++){}
return i;
}
}