求数组中最大子向量
文章目录
问题描述
输入是具有n个浮点数的向量,输出是输入向量的任何连续子向量中的最大和。
最简单的方法是对所有满足i,j在0到n的的整数进行迭代,对每个整数对,程序计算data[i…j]的和,并检验总和是否大于迄今为止最大的总和。
这种方法的复杂度为o(n^3),当n为100000时,要运行10天时间。
那么为了优化这种代码,使用下面三种方法。1234567891011121314151617181920float maxsum1(int l,int u)//时间复杂度o(n^2){ int sumarray[MAX_LENGTH]; sumarray[0] = data[0]; for(int i =l;i<=u;i++) { sumarray[i] = sumarray[i-1]+data[i]; } int sum = 0; int maxsum = 0; for(int i = l;i<=u;i++) { for(int j=l;j<=u;j++) { sum = sumarray[j] - sumarray[i-1]; maxsum = max(sum,maxsum); } } return maxsum;}
|
|
|
|