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