Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1095322
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-09-16 10:59:02


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) |
给主人留下些什么吧!~~

chinaunix网友2010-09-16 16:46:00

很好的, 收藏了 推荐一个博客,提供很多免费软件编程电子书下载: http://free-ebooks.appspot.com