最长子序列和（由浅入深）
O(N^2)
package heng.java.level1;import java.util.Scanner;public class TheMostLongSequenceSum4 {public static void main(String[] args) {Scanner input = new Scanner(System.in);int m = input.nextInt();while(m-->0){int n = input.nextInt();int [] arr = new int [n];for (int i = 0; i < n; i++) {arr[i] = input.nextInt();}int max = maxSubSum(arr);System.out.println(max);}}public static int maxSubSum(int []arr){int maxSum = 0;for (int i = 0; i < arr.length; i++) {int thisSum = 0;for (int j = i; j < arr.length; j++) {thisSum += arr[i];if(thisSum > maxSum){maxSum = thisSum;}}}return maxSum;}}
O(1)
package heng.java.level1;import java.util.Scanner;public class TheMostLongSequenceSum3 {public static void main(String[] args) {Scanner input = new Scanner(System.in);int m = input.nextInt();while(m-->0){int n = input.nextInt();int [] arr = new int [n];for (int i = 0; i < n; i++) {arr[i] = input.nextInt();}int max = maxSubSum(arr);System.out.println(max);}}public static int maxSubSum(int []arr){int maxSum = 0, thisSum = 0;for(int j=0; j<arr.length; j++){thisSum += arr[j];if(thisSum > maxSum){maxSum = thisSum;}else if(thisSum < 0){thisSum = 0;}}return maxSum;}}
O(N)
递归&&分治法：
package heng.java.level1;import java.util.Scanner;public class TheMostLongSequenceSum2 {public static void main(String[] args) {Scanner input = new Scanner(System.in);int m = input.nextInt();while(m-->0){int n = input.nextInt();int [] arr = new int [n];for (int i = 0; i < n; i++) {arr[i] = input.nextInt();}int max = maxSumRec(arr,0,arr.length-1);System.out.println(max);}}public static int maxSumRec(int []arr, int left, int right){if(left == right){if(arr[left] > 0){return arr[left];}else{return 0;}}int center = (left+right)/2;int maxLeftSum = maxSumRec(arr,left,center);int maxRightSum = maxSumRec(arr,center+1,right);int maxLeftBorderSum=0,leftBorderSum=0;for(int i=center; i>=left; i--){leftBorderSum += arr[i];if(leftBorderSum > maxLeftBorderSum){maxLeftBorderSum = leftBorderSum;}}int maxRightBorderSum=0,rightBorderSum=0;for(int i=center+1; i<=right; i++){rightBorderSum += arr[i];if(rightBorderSum > maxRightBorderSum){maxRightBorderSum = rightBorderSum;}}int sum = maxRightBorderSum+maxLeftBorderSum;if(sum < maxLeftSum) sum = maxLeftSum;if(sum < maxRightSum) sum = maxRightSum;return sum;}}