##利用分治法求解（最大子数组问题） 该方法是将数组分割成左右两个子数组，然后利用分治法再分别对左右子数组求解。
public class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) {
return 0;
}
int[] value = new int[prices.length - 1];
for(int i = 0; i < prices.length - 1; i++){
value[i] = prices[i + 1] - prices[i];
}
int max = FindMaxSubArr(value, 0, value.length - 1);
return max > 0 ? max : 0;
}
public int FindMaxSubArr(int[] prices, int low, int high) {
if (low == high) {
return prices[low];
}
else{
int mid = (low + high) / 2;
int leftSum = FindMaxSubArr(prices, low, mid);
int rightSum = FindMaxSubArr(prices, mid + 1, high);
int crossSum = FindMaxCrossSubArr(prices, low, mid, high);
if (leftSum >= rightSum && leftSum >= crossSum) {
return leftSum;
}
else if (rightSum >= leftSum && rightSum >= crossSum) {
return rightSum;
}
else {
return crossSum;
}
}
}
public int FindMaxCrossSubArr(int[] prices, int low, int mid, int high) {
int leftSum = -999999;
int rightSum = -999999;
int sum = 0;
for(int i = mid; i >= low; i--){
sum += prices[i];
if(sum > leftSum){
leftSum = sum;
}
}
sum = 0;
for(int j = mid + 1; j <= high; j++){
sum += prices[j];
if(sum > rightSum){
rightSum = sum;
}
}
return leftSum + rightSum;
}
}
##一个简单的方法 感觉要比分治法简单很多...不明白算法导论上为什么用分治法来求解最大子数组问题
int maxProfit(vector<int> &prices) {
int maxPro = 0;
int minPrice = INT_MAX;
for(int i = 0; i < prices.size(); i++){
minPrice = min(minPrice, prices[i]);
maxPro = max(maxPro, prices[i] - minPrice);
}
return maxPro;
}