浅析连续子向量,子数组和(一维，二维)问题

浅析连续子向量,子数组和(一维，二维)问题

By 钟桓

 9月 16 2014 更新日期:9月 16 2014

1. 1. 最大连续子向量和
   1. 1.0.1. 问题描述：

• 2. 子向量和接近于0
• 3. 收费站问题
• 4. 区间赋值问题
• 5. 二维连续子数组和
• 6. 参考资料：

最大连续子向量和

问题描述：

输入是具有n个浮点数的向量x，输出这个向量的任何连续子向量中的最大和。

简单分析：子向量可以是一个空向量，空向量的和为0；如果向量的所有元素都是负数，最大子向量和就是0；

1 简单分析后，对于这个问题，我们立马能向想到的就是暴力算法，对所有0<=i<=j

解法1：简单粗暴型
int res=0; //答案
for(int i= 0 ; ifor(int j=i;jsum=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;iint sum=0;  for(int j=i;jsum+=x[j];  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！