毫无意义的胡思乱想

木木！ · 2020-01-20 21:06:14 · 个人记录

前言

如何从一道简单的题里面想出一些很没有用的东西？

例题

最大连续子段和

给出 n 个数，求他们的最大连续子段和。

暴力解法

暴力解法是 \Theta(n^3) 的，很好想。

long long ans = 0;
for(int i=1; i<=n; ++i)
{
    for(int j=i; j<=n; ++j)
    {
        long long sum = 0;
        for(int k=i; k<=j; ++k)
        {
            sum += ai[k];
        }
        chkmax(ans,sum);
    }
}

优化途径 1

其中一个优化途径是累积于过往信息。或者，我本人喜欢叫它“站在巨人肩膀上”。时间复杂度 \Theta(n^2)。

long long ans = 0;
for(int i=1; i<n; ++i)
{
    long long sum = 0;
    for(int j=i; j<=n; ++j)
    {
        sum += ai[j];
        chkmax(ans,sum);
    }
}

然后一个优化方式是抛弃无用计算。或者，我本人喜欢叫它“知道你要干什么”。

这一步优化有点跳，十分有拿着答案找过程的感觉。那么，按照这个思路，我们想想我们到底要干什么。我们要找出这个最大子段和，那我们在 sum 是负数的时候，就应该果断 break 掉。因为接下来的加和肯定不是最大子段和了。不仅要 break，而且还要将循环起点提前，因为这些都肯定不是最大子段和了。

整理一下代码，优化一下实现。时间复杂度 \Theta(n)。

long long ans = 0;
long long sum = 0;
for(int i=1; i<=n; ++i)
{
    chkmax(sum,0);
    sum += ai[i];
    chkmax(ans,sum);
}

优化途径 2

第二个优化途径是通过前缀和快速求最大值。前缀和的思想我们暂时不知道。

for(int i=1; i<=n; ++i)
{
   si[i] = si[i-1]+ai[i];
}

long long ans = 0;
for(int i=1; i<=n; ++i)
{
    for(int j=i; j<=n; ++j)
    {
        chkmax(ans,si[j]-si[i-1]);
    }
}

然后一个优化方式还是抛弃无用计算。我们要求出最大子段和，就对于同一个 si[i-1] 要求 si[j] 最大。或者，也可以对于同一个 si[j] 要求 si[i-1] 最小。

for(int i=1; i<=n; ++i)
{
   si[i] = si[i-1]+ai[i];
}

long long sum = 0;
long long minsi = 0;
for(int i=1; i<=n; ++i)
{
    chkmin(minsi,si[i]);
    chkmax(ans,si[i]-minsi);
}

再接一个优化，因为这里 si[i] 可以现场算，那么就可以“现场手工打磨”，剥去多余的预处理。

long long si = 0;
long long ans = 0;
long long minsi = 0;
for(int i=1; i<=n; ++i)
{
    chkmin(minsi,si);
    si += ai[i];
    chkmax(ans,si-minsi);
}

这里的 si-minsi 就等价于上面代码中的 sum，两份代码等价。如果我们只关注 si-minsi 的值的话，下面的代码就等价于上面的代码。

总结

代码等价的话，其蕴含的思想也相同。那么，前缀和就是一种“累积的预处理”。也就相当于“预处理你所要累积的”。

本篇文章所讲的都是一点没有用的东西。