原文地址:求和最大的连续子序列问题分析【原创】作者:向阳的围脖2010
问题:给出一个整形数组a,长度为n,求其和最大的连续字序列。
1 最原始的思路,两个for循环迭代 也是最暴力的解法
best = a[0];
for(i = 0; i
< n; i++){
int
sum = 0;
for(j = i; j < n;
j++){
sum +=
a[j];
if(sum >
best)
best = sum;
}
}
时间复杂度是T(n) = O(n^2)
2 查看了一下别人的优化算法 联机算法 时间复杂度仅为O(n),如下:
sum
= a......
阅读全文