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