动态规划解决最大子数组问题

文章目录

解决方式
时间复杂度
程序范例
总结

问题

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]