O£¨n£©×î´ó×ÓÐòÁÐÎÊÌâ

package algorithm;

/**
 * o(n)µÃµ½×î´ó×ÓÐòÁÐÎÊÌâ
 * @author sai
 *
 */
public class MaxSubSequence {
 public static Integer[] sequence = {10, -2, 3, 10, -4, 7, 2, -5};

 public static void main(String[] args) {
  maxSub();
 }

 public static Integer[] maxSub() {
  int left = 0;
  int right = 0;
  int maxSum = sequence[0];
  int midSeqSum = 0; 
  for (int i = 1; i < sequence.length; ++i) {
   if (right == i - 1) {
    if (sequence[i] >= 0) {
     maxSum += sequence[i];
     ++right;
    } else {
     midSeqSum += sequence[i];
    }
   } else {
    int sum = maxSum + midSeqSum + sequence[i];
    if (sequence[i] >= maxSum && sequence[i] > sum) {
     left = i;
     right = i;
     maxSum = sequence[i];
     midSeqSum = 0;
    } else if (sum >= maxSum && sum >= sequence[i]) {
     right = i;
     maxSum = sum;
     midSeqSum = 0;
    } else {
     midSeqSum += sequence[i];
    }
   }
  }
  System.out.println("left = " + left + "; right = " + right + "\nsum = " + maxSum);
  Integer[] result = new Integer[right - left + 1];
  for (int i = 0; i < result.length; ++i) {
   result[i] = sequence[left + i];
  }
  return result;
 }
}