# 最大子段和问题

## 问题分析：

#### 暴力遍历法：

```int maxSum(int n, int[] a, int besti, int bestj) {
int sum = 0;
for (int i = 1; i <= n; i++) {
int thissum = 0;

for (int j = i; j <= n; j++) {
thissum += a[j - 1];
if (thissum > sum) {
sum = thissum;
besti = i;
bestj = j;
}   // end if
}   // end inner for

}   // end out for

return sum;
}   // end maxSum```

#### 分治法：

• ①和a[1..n/2]的最大字段和相同。
• ②和a[n/2+1:n]的最大字段和相同。
• ③最大字段和包含两部分，一部分在a[1..n/2]中，另一部分在a[n/2+1..n]中。

```static int maxSubSum(int[] a, int left, int right) {
int sum = 0;
if (left == right) {
sum = a[left - 1] > 0 ? a[left - 1] : 0;
} else {
int center = (left + right) / 2;
int leftSum = maxSubSum(a, left, center);
int rightSum = maxSubSum(a, center + 1, right);

int s1 = 0;
int lefts = 0;
for (int i = center; i >= left; i--) {
lefts += a[i - 1];
if (lefts > s1) s1 = lefts;
}

int s2 = 0;
int rights = 0;
for (int i = center + 1; i <= right; i++) {
rights += a[i - 1];
if (rights > s2) s2 = rights;
}

sum = s1 + s2;
if(sum < leftSum) sum = leftSum;
if(sum < rightSum) sum = rightSum;
}   // end if

return sum;
}   // end maxSubSum```

#### 动态规划算法：

```static int maxSum(int n, int[] a) {
int sum = 0, b = 0;
for (int i = 1; i <= n; i++) {
if (b > 0) b += a[i - 1];
else b = a[i - 1];
if (b > sum) sum = b;
}

return sum;
}```

105 篇文章48 人订阅

0 条评论

36370

20450

24640

32950

31560

13830

37360

35960

45170

17430