1.最原始,最古老,最暴力的方法。。。
best = a[1];
for(i = 1; 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.第一次优化:利用“连续子序列之和等于两个前缀和之差”
best = s[1]; //引入的s数组中存放的是前缀和
for(int i = 1; i <= n; i++)
for(int j = i; j<= n; j++)
{
best = (best > (s[j] - s[i])? best : (s[j] - s[i])); //更新最大值
}
时间复杂度为:T(n) = O(n^2)
3.再次优化:分治法
int maxsum(int *a, int x, int y)
{
int i, m, v, L, R, max;
if(y-x == 1)
return a[x];
m = x + (y-x)/2;
max = maxsum(a, x, m) > maxsum(a, m, y) ? maxsum(a, x, m) : maxsum(a, m, y);
v = 0;
L = a[m-1];
for(int i = m-1; i >= x; i--)
{
v += a[i];
L = L > v? L: v;
}
v = 0;
R = a[m];
for(int i = m; i < y; i++)
{
v += a[i];
R = R > v? R: v;
}
return max > (L+R)? max: (L+R);
}
时间复杂度: T(n) = O(n*logn)
4.继续优化
DP, 联机算法:
sum = a[1], temp = a[1];
for(int i = 2; i <= n; i++)
{
if(sum > 0)
temp += a[i];
else
temp = a[i];
if(temp > sum)
sum = temp;
}
时间复杂度: T(n) = O(n)
附:
如果在任何时刻,算法都能对它已经读入的数据给出子序列问题的正确答案,具有这种特性的算法叫做联机算法。仅需要常量空间并以线形时间运行的联机算法几乎是完美的算法。
一个经典的问题:求最大子序列和的算法就是这样一个完美的算法
阅读(2534) | 评论(1) | 转发(0) |