2.14 求数组的子数组之和的最大值

本文主要是介绍2.14 求数组的子数组之和的最大值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：给定一个一维数组，求这个数组的子数组之和的最大值。


最佳方法：动态规划！


一、
可以将一个大问题（N个元素数组）转化为一个较小的问题（N-1个元素数组）。。
假设已经知道（A[1],...A[n-1]）中最大的子数组的和为：All[1]
并且已经知道（A[1],...A[n-1]）中包括A[1]的子数组的最大和为start[1]


所以最终的解All[0] = max(A[0], A[0]+start[1], All[1])
所以通过DP来求解！

代码如下：

#include <iostream>
#define MAXN 10000using namespace std;int A[MAXN], n, start[MAXN], All[MAXN];int max(int x, int y) {return x > y ? x : y;
}int MaxSum(int *A, int n) {start[n - 1] = A[n - 1];All[n - 1] = A[n - 1];for(int i = n-2; i >= 0; --i) {start[i] = max(A[i], start[i + 1] + A[i]);All[i] = max(All[i + 1], start[i]);}return All[0];
}int main() {cin >> n;for(int i = 0; i < n; ++i) cin >> A[i];cout << MaxSum(A, n) << endl;return 0;
}

二、
上面那种方法时间复杂度为：O(N)，但是空间复杂度不热观。
所以下面寻求空间复杂度为O（1）的算法。


思路：由上面那两个递推式
start[i] = max(A[i], start[i + 1] + A[i]);
All[i] = max(All[i + 1], start[i]);
      可以知道：（1）如果start[i + 1] < 0，那么start[i] = A[i]
（2）start[i + 1]只有在计算start[i]的时候才能用到。
        All[i + 1]只有在计算All[i]的时候才能用到。


所以可以有一种时间复杂度是O(N),而空间复杂度是O(1)的算法。


代码：

#include <iostream>
#define MAXN 10000using namespace std;int A[MAXN], n, start[MAXN], All[MAXN];int max(int x, int y) {return x > y ? x : y;
}int MaxSum(int *A, int n) {int nStart = A[n-1];int nAll = A[n-1];for(int i = n-2; i >= 0; --i) {nStart = max(A[i] + nStart, A[i]);nAll = max(nStart, nAll);}return nAll;
}int main() {cin >> n;for(int i = 0; i < n; ++i) cin >> A[i];cout << MaxSum(A, n) << endl;return 0;
}

三、
当然还有最后一种最简单的写法：

代码：

#include <iostream>
#define MAXN 10000using namespace std;int A[MAXN], n, start[MAXN], All[MAXN];int max(int x, int y) {return x > y ? x : y;
}int MaxSum(int *A, int n) {int nStart = A[n-1];int nAll = A[n-1];for(int i = n-2; i >= 0; --i) {if(nStart < 0) nStart = 0;nStart += A[i];if(nStart > nAll) nAll = nStart;}return nAll;
}int main() {cin >> n;for(int i = 0; i < n; ++i) cin >> A[i];cout << MaxSum(A, n) << endl;return 0;
}

这篇关于2.14 求数组的子数组之和的最大值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---