中国煤炭建设协会网站,网站开发 就业简历模板,汕头建设银行各支行电话,网站建设费走什么费用给定一个数组#xff0c;求它的最大连续子列和。这个问题有四种解法。 1、暴力循环(O(n^3))分析这个问题#xff0c;既然是子列#xff0c;那么它最长为n#xff0c;最短为1。要想求和我们一般需要知道这个子列的左端下标和右端下标#xff0c;再求这个子列的和。最简单的…给定一个数组求它的最大连续子列和。这个问题有四种解法。 1、暴力循环(O(n^3))分析这个问题既然是子列那么它最长为n最短为1。要想求和我们一般需要知道这个子列的左端下标和右端下标再求这个子列的和。最简单的办法就是用暴力循环来求和。首先我们需要定义左端下标i每次循环i。接下来是右端下标jj的初值为i因为右端下标总是大于等于左端下标每次循环j。知道了左端下标i和右端下标j之后再从i到j循环求和就行了。#include iostream
#include algorithmusing namespace std;const int N1*10^6;int main()
{int n;cinn;int a[N];int sum0,maxsum0;for(int i0;in;i) cina[i];for(int i0;in;i){for(int ji;jn;j){sum0;for(int ki;kj;k) suma[k];if(summaxsum) maxsumsum;}}coutmaxsum;return 0;
} 2、暴力循环的改进(O(n^2))第一种算法显然时间复杂度太高了可以进行改进减少一层循环。当左端下标i和右端下标j确定时知道a[i]~a[j]的和如果要求a[i]~a[j1],按照第一种算法需要重新遍历一遍a[i]~a[j]的数组再把a[j1]加上。思考后我们发现如果已知a[i]~a[j]的和sum我们只需要让suma[j1]就可以得到a[i]~a[[j1]的和。因此我们就可以使用两层循环就可以解决这个问题。#include iostream
#include algorithmusing namespace std;const int N1*10^6;int main()
{int n;cinn;int a[N];int sum0,maxsum0;for(int i0;in;i) cina[i];for(int i0;in;i){sum0;for(int ji;jn;j){suma[j];if(summaxsum) maxsumsum;}}coutmaxsum;return 0;
}值得注意的是第一个算法中sum重置为0是在第二个循环里第二个sum重置为0是在第一层循环里。原因是第一个算法的第三层循环是循环累加求值所以每次循环前要重置为0而第二个算法简化后左端i确定后利用累加的方法记录以左端i为首长度为1~n-i1的各子列的和所以在第一重循环确定新的左端i后就要重置sum。3、分治(O(n*logn))当我们看到一个算法的时间复杂度是O(n^2)的时候我们就可以思考这个算法能不能经过改进将时间复杂度降为O(n*logn)这个问题也可以用分治的方法来解决。(有时候想想这些算法题真操蛋万物可分治可二分可递归了^_^)分治是将大的问题划分成小的问题最后整合结果的方法。分是划分治是整合结果。怎么分治呢我们考虑到把整个数列从中间切开最大子列和max(左边数列最大子列和,右边数列子列和跨越边界的子列和)跨越边界的子列和就是左右两边的数都包含的情况。利用这个办法不断地将子列切片进行分治最终就能求得整个数列的最大子列和。代码有点复杂回头有空再写吧^_^4、在线处理(O(n))!这是对于最大子列和最好最快的算法。这个算法的思想是从左到右累加每个数得到sum如果summaxsum更新maxsumsum如果sum0将sum重置为0。输出最后的sum值。为什么这个算法是正确的呢如果任意一个子列和小于0那么这个子列一定不会位于和最大子列的左侧因为一个负数对于整个数列的和是没有贡献的。#include iostream
#include algorithmusing namespace std;const int N1*10^6;int main()
{int n;cinn;int a[N];int sum0,maxsum-1*10^6;for(int i0;in;i){cina[i];suma[i];if(sum0) sum0;if(summaxsum) maxsumsum;}coutmaxsum;return 0;
}为什么我把maxsum设为负数呢因为有的算法题给的数据实在变态你必须考虑符合题意的每一种极端情况。把maxusm设置为负数我是考虑到只有一个元素且为负数的情况。为什么它叫在线处理呢因为它可以边输入边计算只需要一个循环。而算法复杂度只能这么小了毕竟输入数据的算法也需要O(n)。这四种算法思想均来自中国大学mooc陈越老师的数据结构课。md真爽还有啥比ac更爽的纠结这么久终于找到bug解决这道题了。
