# 最大子列和问题

## 常用方法

```    public static int MaxSubseqSum1(int[] A, int N) {
int ThisSum, MaxSum = 0;
int i, j, k;
for (i = 0; i < N; i++) {
for (j = i; j < N; j++) {
ThisSum = 0;
for (k = i; k <= j; k++) {
ThisSum += A[k];
}
if (ThisSum > MaxSum) {
MaxSum = ThisSum;
}
}
}
return MaxSum;
}```

```    public static int MaxSubseqSum2(int[] A, int N) {
int ThisSum;
int MaxSum = 0;
int i, j;
for (i = 0; i < N; i++) {
ThisSum = 0;
for (j = i; j < N; j++) {
ThisSum += A[j];
if (ThisSum > MaxSum) {
MaxSum = ThisSum;
}
}
}
return MaxSum;
}```

## 分治法

```    /**
* 分治法，保持API一致
* @param A 求解数列
* @param N 元素总数
* @return
*/
public static int MaxSubseqSum3(int[] A, int N) {
return DivideAndConquer(A, 0, N-1);
}

/**
* 分治法主体
* @param List 求解数列
* @param left 左半边的下标
* @param right 右半边的下标
* @return 所求数列的最大子列和
*/
public static int DivideAndConquer(int[] List, int left, int right) {
int MaxLeftSum, MaxRightSum;
int MaxLeftBorderSum, MaxRightBorderSum;
int LeftBorderSum, RightBorderSum;
int center, i;

if (left == right) {
if (List[left] > 0) {
return List[left];
} else {
return 0;
}
}

center = (left + right) / 2;

//分解数列 不断递归调用
MaxLeftSum = DivideAndConquer(List, left, center);
MaxRightSum = DivideAndConquer(List, center + 1, right);

//分别结算左右两边的跨越边界的和
MaxLeftBorderSum = 0; LeftBorderSum = 0;
for (i = center; i >= left; i--) {
LeftBorderSum += List[i];
if (LeftBorderSum > MaxLeftBorderSum) {
MaxLeftBorderSum = LeftBorderSum;
}
}

MaxRightBorderSum = 0; RightBorderSum = 0;
for (i = center + 1; i <= right; i++) {
RightBorderSum += List[i];
if (RightBorderSum > MaxLeftBorderSum) {
MaxRightBorderSum = RightBorderSum;
}
}
return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
}

/**
* 取三个数中的最大值
* @return int
*/
private static int Max3(int A, int B, int C) {
return A > B ? A > C ? A : C : B > C ? B : C;
}```

```T(1) = O(1)
T (N) = 2T(N/2) + cN
= 2 [2T( N/22 ) + cN/2] + cN
= 2kO(1) + ckN
= O(NlogN )```

## 在线处理

```    public static int MaxSubseqSum4(int[] A, int N) {
int ThisSum, MaxSum;
int i;
ThisSum = MaxSum = 0;
for (i = 0; i < N; i++) {
ThisSum += A[i];
if (ThisSum > MaxSum) {
MaxSum = ThisSum;
} else if (ThisSum < 0) {
ThisSum = 0;
}
}
return MaxSum;
}```

```    public static void main(String[] args) {
int size = 31;
int[] testArr = {3, -1, 5, 10, -8, 2, 1, 4, 0, 7, -5, -6, 3, -8, -10,
10, -20, -8, 0, 3, 0, -9, -10, 5, 3, 0, -8, 10, -4, 10, -7};
int runCount = 100000;
testFunction1(testArr, size, runCount);
testFunction2(testArr, size, runCount);
testFunction3(testArr, size, runCount);
testFunction4(testArr, size, runCount);
}```

```Max Subsequence Sum 1 is 23
function1 run time is  738ms
Max Subsequence Sum 2 is 23
function2 run time is  44ms
Max Subsequence Sum 3 is 17
function3 run time is  110ms
Max Subsequence Sum 4 is 17
function4 run time is  54ms```

121 篇文章32 人订阅

0 条评论

## 相关文章

244100

### 码农眼中的数学之～数学基础

1维直线、2维平面（长宽）、3维空间（长宽高 | xyz轴）、4维时空（xyz轴+时间轴）

13430

### 程序员进阶之算法练习（三十）附基础教程

BAT常见的算法面试题解析：程序员算法基础——动态规划程序员算法基础——贪心算法工作闲暇也会有在线分享，算法基础教程-。

25130

13530

40460

9130

21190

45550

6510

639100