问题描述
给定一数组，求出此数组的最大连续子数组中元素之和
样例
INPUT
-5, -4, 5, 3, 2, 6, -1, -2, 6, -9
OUTPUT
22
分治解法
最大子数组可能有三种情况：
- 最大子数组完全位于中点左边
- 最大子数组完全位于中点右边
- 最大子数组跨越中点
因此我们可以采取分治法，逐步将问题分解。
不难看出，对于前两种情况，我们可以将其视为”求一个更小数组上的最大子数组”问题。所以，不断进行递归调用直到数组大小为1即可解决前两种情况。
对于第三种情况，由于已知最大子数组必定跨越中点，而且一定是连续的，所以我们可以分别求出以中点为端点的左右两部分的最大子数组之和，再相加，就得到第三种情况的解。
代码和注释如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
//use recursive #include <iostream> using namespace std; //定义宏，表示最小值 #define MIN -2000000000 //找出三个数的最大值 int findMaxInThree(int a, int b, int c) { int res = a >= b ? a : b; res = res >= c ? res : c; return res; } //找出跨越中点时的最大子数组 //分为左右两侧，分别从中点向两端累加，不断更新最大和 //最后再将两侧的最大和相加 //注意中点不要加两次 int findMaxCrossArray(int a[], int be, int mid, int en) { int res_l = MIN, res_r = MIN; [crayon-597af8259b9f2465418974 ]<code>int temp = 0; for (int i = mid; i >= be; i--){ temp += a[i]; if (temp > res_l) res_l = temp; } temp = 0; for (int i = mid + 1; i <= en; i++){ temp += a[i]; if (temp > res_r) res_r = temp; } return res_l + res_r; |
[/crayon]
}
//找最大子数组
//分为三种情况：
//1、最大子数组完全位于中点左边
//2、最大子数组完全位于中点右边
//3、最大子数组跨越中点
//前两种情况可以递归调用此函数，当be大于等于en时结束递归
//第三种情况调用findMaxCrossArra()函数解决
//最后调用findMaxInThree()返回三种情况的最大值，即为最大子数组的和
int findMaxSubArray(int a[], int be, int en)
{
if (be >= en) return a[en];
|
1 2 3 4 5 6 |
[crayon-597af8259ba01161741828 ]int mid = (be + en) / 2; int max_l = findMaxSubArray(a, be, mid); int max_r = findMaxSubArray(a, mid + 1, en); int max_c = findMaxCrossArray(a, be, mid, en); return findMaxInThree(max_l, max_r, max_c); |
[/crayon]
}
int main()
{
int test[10] = {
-5, -4, 5, 3, 2, 6, -1, -2, 6, -9
};
|
1 2 |
[crayon-597af8259ba14350280854 ]cout << findMaxSubArray(test, 0, 9) << endl; return 0; |
[/crayon]
}
动态规划解法
此问题还有渐进时间复杂度为O(n)的动态规划解法。
代码和注释如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
//max-subarray problem //use dynamic programming #include<iostream> #include<cstring> using namespace std; const int MAXN = 1050; const int N_INF = -0x7F7F7F; int input_array[MAXN]; int max_two_int(int a, int b){ return a > b ? a : b; } int dp(int n){ int maxsum = N_INF, sum = 0; for (int i = 0; i < n; i++) { sum = max_two_int(sum + input_array[i], input_array[i]); maxsum = max_two_int(maxsum, sum); } return maxsum; } int main() { [crayon-597af8259ba21479833841 ]<code>int n; while(cin >> n) { memset(input_array, 0, sizeof(input_array)); for (int i = 0; i < n; i++){ cin >> input_array[i]; } cout << dp(n) << endl; } |
[/crayon]
}
不错不错