最大子序列和的问题的解(1)
最暴力的做法，复杂度O(N^3)
暴力求解也是容易理解的做法，简单来说，我们只要用两层循环枚举起点和终点，这样就尝试了所有的子序列，然后计算每个子序列的和，然后找到其中最大的即可，C语言代码如下：
-
#include <stdio.h>
-
-
//N是数组长度，num是待计算的数组，放在全局区是因为可以开很大的数组
-
int N, num[1024];
-
-
int main()
-
{
-
//输入数据
-
scanf("%d", &N);
-
for(int i = 1; i <= N; i++)
-
scanf("%d", &num[i]);
-
-
int ans = num[1]; //ans保存最大子序列和，初始化为num[1]能保证最终结果正确
-
//i和j分别是枚举的子序列的起点和终点，k所在循环计算每个子序列的和
-
for(int i = 1; i <= N; i++) {
-
for(int j = i; j <= N; j++) {
-
int s = 0;
-
for(int k = i; k <= j; k++) {
-
s += num[k];
-
}
-
if(s > ans) ans = s;
-
}
-
}
-
printf("%d\n", ans);
-
-
return 0;
-
}
如果我们有这样一个数组sum，sum[i]表示第1个到第i个数的和。那么我们如何快速计算第i个到第j个这个序列的和？对，只要用sum[j] - sum[i-1]就可以了！这样的话，我们就可以省掉最内层的循环，让我们的程序效率更高！C语言代码如下：
-
include <stdio.h>
-
-
//N是数组长度，num是待计算的数组，sum是数组前缀和，放在全局区是因为可以开很大的数组
-
int N, num[16384], sum[16384];
-
-
int main()
-
{
-
//输入数据
-
scanf("%d", &N);
-
for(int i = 1; i <= N; i++)
-
scanf("%d", &num[i]);
-
-
//计算数组前缀和
-
sum[0] = 0;
-
for(int i = 1; i <= N; i++) {
-
sum[i] = num[i] + sum[i - 1];
-
}
-
-
int ans = num[1]; //ans保存最大子序列和，初始化为num[1]能保证最终结果正确
-
//i和j分别是枚举的子序列的起点和终点
-
for(int i = 1; i <= N; i++) {
-
for(int j = i; j <= N; j++) {
-
int s = sum[j] - sum[i - 1];
-
if(s > ans) ans = s;
-
}
-
}
-
printf("%d\n", ans);
-
-
return 0;
-
}
这个算法的时间复杂度是O(N^2)。如果我们的计算机可以每秒计算一亿次的话，这个算法在一秒内能计算出10000左右长度序列的答案，比之前的程序已经有了很大的提升！此外，我们在这个程序中创建了一个sum数组，事实上，这也是不必要的，我们我就也可以把数组前缀和直接计算在num数组中，这样可以节约一些内存。
换个思路，继续优化
你应该听说过分治法，正是：分而治之。我们有一个很复杂的大问题，很难直接解决它，但是我们发现可以把问题划分成子问题，如果子问题规模还是太大，并且它还可以继续划分，那就继续划分下去。直到这些子问题的规模已经很容易解决了，那么就把所有的子问题都解决，最后把所有的子问题合并，我们就得到复杂大问题的答案了。可能说起来简单，但是仍不知道怎么做，接下来分析这个问题：
首先，我们可以把整个序列平均分成左右两部分，答案则会在以下三种情况中：
1、所求序列完全包含在左半部分的序列中。
2、所求序列完全包含在右半部分的序列中。
3、所求序列刚好横跨分割点，即左右序列各占一部分。
前两种情况和大问题一样，只是规模小了些，如果三个子问题都能解决，那么答案就是三个结果的最大值。我们主要研究一下第三种情况如何解决：
我们只要计算出：以分割点为起点向左的最大连续序列和、以分割点为起点向右的最大连续序列和，这两个结果的和就是第三种情况的答案。因为已知起点，所以这两个结果都能在O(N)的时间复杂度能算出来。
递归不断减小问题的规模，直到序列长度为1的时候，那答案就是序列中那个数字。
综上所述，C语言代码如下，递归实现：
-
#include <stdio.h>
-
-
//N是数组长度，num是待计算的数组，放在全局区是因为可以开很大的数组
-
int N, num[16777216];
-
-
int solve(int left, int right)
-
{
-
//序列长度为1时
-
if(left == right)
-
return num[left];
-
-
//划分为两个规模更小的问题
-
int mid = left + right >> 1;
-
int lans = solve(left, mid);
-
int rans = solve(mid + 1, right);
-
-
//横跨分割点的情况
-
int sum = 0, lmax = num[mid], rmax = num[mid + 1];
-
for(int i = mid; i >= left; i--) {
-
sum += num[i];
-
if(sum > lmax) lmax = sum;
-
}
-
sum = 0;
-
for(int i = mid + 1; i <= right; i++) {
-
sum += num[i];
-
if(sum > rmax) rmax = sum;
-
}
-
-
//答案是三种情况的最大值
-
int ans = lmax + rmax;
-
if(lans > ans) ans = lans;
-
if(rans > ans) ans = rans;
-
-
return ans;
-
}
-
-
int main()
-
{
-
//输入数据
-
scanf("%d", &N);
-
for(int i = 1; i <= N; i++)
-
scanf("%d", &num[i]);
-
-
printf("%d\n", solve(1, N));
-
-
return 0;
-
}
不难看出，这个算法的时间复杂度是O(N*logN)的（想想归并排序）。它可以在一秒内处理百万级别的数据，甚至千万级别也不会显得很慢！这正是算法的优美之处。对递归不太熟悉的话可能会对这个算法有所疑惑，那可就要仔细琢磨一下了。
动态规划的魅力，O(N)解决！
很多动态规划算法非常像数学中的递推。我们如果能找到一个合适的递推公式，就能很容易的解决问题。
我们用dp[n]表示以第n个数结尾的最大连续子序列的和，于是存在以下递推公式：dp[n] = max(0, dp[n-1]) + num[n]
仔细思考后不难发现这个递推公式是正确的，则整个问题的答案是max(dp[m]) | m∈[1, N]。C语言代码如下：
-
#include <stdio.h>
-
-
//N是数组长度，num是待计算的数组，放在全局区是因为可以开很大的数组
-
int N, num[134217728];
-
-
int main()
-
{
-
//输入数据
-
scanf("%d", &N);
-
for(int i = 1; i <= N; i++)
-
scanf("%d", &num[i]);
-
-
num[0] = 0;
-
int ans = num[1];
-
for(int i = 1; i <= N; i++) {
-
if(num[i - 1] > 0) num[i] += num[i - 1];
-
else num[i] += 0;
-
if(num[i] > ans) ans = num[i];
-
}
-
-
printf("%d\n", ans);
-
-
return 0;
-
}
这里我们没有创建dp数组，根据递归公式的依赖关系，单独一个num数组就足以解决问题，创建一个一亿长度的数组要占用几百MB的内存！这个算法的时间复杂度是O(N)的，所以它计算一亿长度的序列也不在话下！不过你如果真的用一个这么大规模的数据来测试这个程序会很慢，因为大量的时间都耗费在程序读取数据上了！
另辟蹊径，又一个O(N)的算法
考虑我们之前O(N^2)的算法，即一个简单的优化一节，我们还有没有办法优化这个算法呢？答案是肯定的！
我们已知一个sum数组，sum[i]表示第1个数到第i个数的和，于是sum[j] - sum[i-1]表示第i个数到第j个数的和。
那么，以第n个数为结尾的最大子序列和有什么特点？假设这个子序列的起点是m，于是结果为sum[n] - sum[m-1]。并且，sum[m]必然是sum[1],sum[2]...sum[n-1]中的最小值！这样，我们如果在维护计算sum数组的时候，同时维护之前的最小值， 那么答案也就出来了！为了节省内存，我们还是只用一个num数组。C语言代码如下：
-
#include <stdio.h>
-
-
//N是数组长度，num是待计算的数组，放在全局区是因为可以开很大的数组
-
int N, num[134217728];
-
-
int main()
-
{
-
//输入数据
-
scanf("%d", &N);
-
for(int i = 1; i <= N; i++)
-
scanf("%d", &num[i]);
-
-
//计算数组前缀和，并在此过程中得到答案
-
num[0] = 0;
-
int ans = num[1], lmin = 0;
-
for(int i = 1; i <= N; i++) {
-
num[i] += num[i - 1];
-
if(num[i] - lmin > ans)
-
ans = num[i] - lmin;
-
if(num[i] < lmin)
-
lmin = num[i];
-
}
-
-
printf("%d\n", ans);
-
-
return 0;
-
}
看起来我们已经把最大连续子序列和的问题解决得很完美了，时间复杂度和空间复杂度都是O(N)，不过，我们确实还可以继续！
大道至简，最大连续子序列和问题的完美解决
很显然，解决此问题的算法的时间复杂度不可能低于O(N)，因为我们至少要算出整个序列的和，不过如果空间复杂度也达到了O(N)，就有点说不过去了，让我们把num数组也去掉吧！
-
#include <stdio.h>
-
-
int main()
-
{
-
int N, n, s, ans, m = 0;
-
-
scanf("%d%d", &N, &n); //读取数组长度和序列中的第一个数
-
ans = s = n; //把ans初始化为序列中的的第一个数
-
for(int i = 1; i < N; i++) {
-
if(s < m) m = s;
-
scanf("%d", &n);
-
s += n;
-
if(s - m > ans)
-
ans = s - m;
-
}
-
printf("%d\n", ans);
-
-
return 0;
-
}
文章来源: xintiaobao.blog.csdn.net，作者：心跳包，版权归原作者所有，如需转载，请联系作者。
原文链接：xintiaobao.blog.csdn.net/article/details/89473026
- 点赞
- 收藏
- 关注作者
评论（0）