![]()
2.5 最⼤连续⼦数组和 🚀🔢
题目描述:
给定⼀个整数数组，数组⾥可能有正数、负数和零。数组中连续的⼀个或多个整数组成⼀个⼦数组，每个⼦数组都有⼀个和。求所有⼦数组的和的最⼤值。例如，如果输⼊的数组为{1, −2, 3, 10, −4,
7, 2, −5}，和最⼤的⼦数组为{3, 10, −4, 7, 2}，那么输出为该⼦数组的和18。
题⽬解析:
解法⼀：蛮⼒枚举 💪🤖
要求解一个数组的最大连续子数组和，最直观、最野蛮的方法是使用三个for循环三层遍历，求出数组中每一个子数组的和，最终找出这些子数组和中的最大值。令 currSum[i,…, j] 为数组 A 中第 i 个元素到第 j 个元素的和（其中 0≤i≤j maxSum) {
maxSum = currSum;
}
// 这里要记得清零，否则 sum 最终存放的是所有子数组的和
currSum = 0;
}
}
return maxSum;
}
```
这种方法的时间复杂度为 O(n^3)。
解法⼆：动态规划 🧠📈
事实上，我们可以令 currSum 表示以当前元素结尾的最大连续子数组的和，maxSum 表示全局的最大子数组的和。当往后扫描时，对第 j 个元素有两种选择，要么放入前面找到的子数组，要么作为新子数组的第一个元素。如果 currSum > 0，则令 currSum 加上 A[j]；如果 currSum < 0，则 currSum 被置为当前元素，即 currSum = A[j]。这相当于是说，如果设 currSum(j) 为以 j 结尾的最大连续子数组的和，那么 currSum(j) = max{0, currSum[j−1]} + A[j]。如果 maxSum < currSum，则更新 maxSum = currSum；否则 maxSum 保持原值，不更新。举个例子，如果输入数组是 {1, −2, 3, 10, −4, 7, 2, −5}，那么 currSum 和 maxSum 的变化分别为：
currSum：0→1→-1→3→13→9→16→18→13；
maxSum：0→1→1→3→13→13→16→18→18
参考代码如下：
```c
int MaxSubArray(int* A, int n) {
int currSum = 0;
int maxSum = A[0]; // 数组元素全为负的情况，返回最大数
for (int j = 0; j < n; j++) {
if (currSum >= 0) {
currSum += A[j];
} else {
currSum = A[j];
}
if (currSum > maxSum) {
maxSum = currSum;
}
}
return maxSum;
}
```
这个方法从前往后扫描一遍数组，即可求得最大连续子数组和，时间复杂度为 O(n)。 🚀📊
希望这些解法能帮助你更专业地理解并解决这个问题！如果有任何疑问或需要进一步的解释，请随时提出。 💡👨💻
标签：
