算法导论之求股票最大收益

股票的最大收益的起点 start和终点end；x，y等是中间点。
end - start = end - x + x - y +y +..... -end
把股票的点数组转成连续点区间数组，然后找区间数组的最大子数组，起点和终点就是两个边界都分别加1。

package com.cammsia;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/** * Created by cammsia on 16/9/11. */
public class Test {  
  public static void main(String[] args) {   
   int a[] = { -47, 10, 23, 4, 3, 4, 3, 2, 46, 5, 5 };  
   int b[] = new int[a.length -1];    
   for (int i = 0; i < a.length-1; i++) {     
     b[i] = a[i+1] - a[i];   
   } 
   int maxSum = 0;  
   int curSum = 0;  
   int endIndex = 0;  
  int startIndex = 0;   
  for (int i = 0; i < b.length; i++) {   
     curSum += b[i];     
     //找終点     
    if (curSum > maxSum) {     
     endIndex = i + 2;    
     maxSum = curSum;     
    }    
   //找起点     
   if (curSum < 0) {     
    startIndex = i + 2;    
    curSum = 0;    
   }    
}    
System.out.println(startIndex + ":" + endIndex);    System.out.println(maxSum); 
 }}