- 1. 最大连续子向量和
- 1.0.1. 问题描述:
- 2. 子向量和接近于0
- 3. 收费站问题
- 4. 区间赋值问题
- 5. 二维连续子数组和
- 6. 参考资料:
最大连续子向量和
问题描述:
输入是具有n个浮点数的向量x,输出这个向量的任何连续子向量中的最大和。
简单分析:子向量可以是一个空向量,空向量的和为0;如果向量的所有元素都是负数,最大子向量和就是0;
1 简单分析后,对于这个问题,我们立马能向想到的就是暴力算法,对所有0<=i<=j<n的整数对进行迭代。对每个整数对(i,j),程序都要计算x[i…j]的总和,并判断其是否大于当前的最大总和。
解法1:简单粗暴型
int res=0; //答案
for(int i= 0 ; i<n;i++)for(int j=i;j<n;j++){sum=0for(int k=i;k<=j;k++) sum+=x[k]res=max(res,sum) }
2 怎么看,上面的算法都是简单粗暴型,O(n^3)的时间复杂度实在不敢恭维,数据量一大,时间上实在不能容忍。那么有没有稍微优雅一点的?我们发现后面的部分有重复计算的,那么我们如何节省它~~一种就是从i开始往前加的时候,每次都记录下来。直接看代码:
解法2:
int res=0; //答案
for(int i=0;i<n;i++)
{int sum=0; for(int j=i;j<n;j++){