homework-01

我选择的书是代码大全

一. 程序的架构和思路：

朴素算法就是一个三重循环，但是当n极大的时候，时间会爆表。

#include<iostream>
#include<cstdio>
using namespace std;
int max(int x,int y)
{
    if (x > y) return x;
    else return y;
}
int main()
{
    int n,a[10010];
    int i,j,k,ans,temp;
    while (scanf("%d",&n) != EOF)
    {
        for (i = 0;i < n;i++) scanf("%d",&a[i]);
        ans = a[0];//确定下界
        for (i = 0;i < n;i++)
        for (j = i;j < n;j++)
        {
            temp = 0;
            for (k = i;k <= j;k++) temp = temp + a[k];//累加
            ans = max(ans,temp);
        }
        printf("%d

",ans);
    }
    return 0;
}

此算法容易理解，时间复杂度为O(n^3)。

继续想其他优化，其实这个可以看做两个求和问题，求i到j的和可以看做1到j的和减去1到i的和，于是可用树状数组优化。

等等...不会这么复杂吧...

利用树状数组优化可将时间复杂度降至O(n^2*(logn)^2)，还是有点大，而且代码量太长，效率不够高。

回看第一种方法，其做了很多冗余的操作，例如，先计算i到j，之后继续计算i到j+1，于是可从上一步的值过渡到下一步，因此也就可以消掉一重循环。

#include<iostream>
#include<cstdio>
using namespace std;
int max(int x,int y)
{
    if (x > y) return x;
    else return y;
}
int main()
{
    int n,a[10010];
    int i,j,ans,sum;
    while (scanf("%d",&n) != EOF)
    {
        for (i = 0;i < n;i++) scanf("%d",&a[i]);
        ans = a[0];//确定下界 
        for (i = 0;i < n;i++)
        {
            sum = 0;
            for (j = i;j < n;j++)
            {
                sum = sum + a[j];//从上一步继续加 
                ans = max(ans,sum);
            }
        }
        printf("%d

",ans);
    }
    return 0;
}

由此可见，此算法时间复杂度为O(n^2)，但是n极大的时候依旧会爆表，所以，我觉得能继续优化。

如果我们不需要知道最大子序列位置的话，i循环似乎就没有用了。

若i到j为最大子序列，那么a[i]不可能为负，因为若a[i]为负，a[i+1]为正，则i+1到j为最大。

所以我们可以这么认为，若枚举到i到j阶段时，此阶段和为0，则可舍去，最大子序列必不包含此阶段。

不过需要注意的是，若a数组全为负，则程序输出为0，于是需要加个一重循环特判下界。

#include<iostream>
#include<cstdio>
using namespace std;
int max(int x,int y)
{
    if (x > y) return x;
    else return y;
}
int main()
{
    int n,a[10010];
    int i,ans,sum;
    while (scanf("%d",&n) != EOF)
    {
        for (i = 0;i < n;i++) scanf("%d",&a[i]);
        ans = a[0];
        for (i = 1;i < n;i++) ans = max(ans,a[i]);//特判下界 
        sum = 0;ans = 0;
        for (i = 0;i < n;i++)
        {
            sum = sum + a[i];
            if (sum > ans) ans = sum;
            else if (sum < 0) sum = 0;//若小于0则舍去 
        }
        printf("%d

",ans);
    }
    return 0;
}