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