问题
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
问题来自于Leetcode:Maximum Subarray
解决方式
利用动态规划思想来解决最大子数组问题。之前的文章有写过有关动态规划的思路。如果你对动态规划不清楚可以通过这篇文章来简单了解下，里面有相应的视频还是不错的：拆分集合为两个和相等的子集合问题（动态规划）。
该方法相对于分治法策略解决最大子数组问题来解决的时间复杂度中会有很大提升。
时间复杂度
O(n)
程序范例
[code lang=”cpp”]
#include <iostream>
int solve(int* a, int length) {
int sum = a[0];
for (int i = 1; i < length; i++) {
if (a[i] < a[i] + a[i – 1]) {
a[i] = a[i] + a[i – 1];
}
if (sum < a[i]) {
sum = a[i];
}
}
return sum;
}
int main() {
int a[10] = {2, 4, -10, 6, 30, 4, 3, -10, 32, 10};
std::cout<<solve(a, 10);
return 0;
}
[/code]
总结
能够利用动态规划思路来解决的问题的特性主要有两点：
- 重叠子问题（overlapping sub-problem）- 即当前状态的解取决于上一个状态的解
- 最优子结构（optimal sub-structure）- 求的解释问题的最有子解
文章来源：胡旭博客 => 动态规划解决最大子数组问题
参考文章：算法导论（p74 练习题4.1-5）
转载请注明出处，违者必究！