每周一算法：最大连续子序列

最大连续子序列

上一篇博文介绍了如何求最大连续子序列的和，每周一算法：最大连续子序列的和。下面继续来看如何求解方案，也就是求最大子序列的开始和结束位置。

题目链接

最大连续子序列

题目描述

给定 $K$ 个整数的序列 { N 0 , N 1 , … , N K ? 1 } \{N_0,N_1,…,N_{K-1}\} {N0?,N1?,…,NK?1?}，其任意连续子序列可表示为 { N i , N i + 1 , … , N j } \{N_i,N_{i+1},…,N_j\} {Ni?,Ni+1?,…,Nj?}，其中 $0\le i\le j<K$。

最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列 { ? 2 , 11 , ? 4 , 13 , ? 5 , ? 2 } \{?2,11,?4,13,?5,?2\} {?2,11,?4,13,?5,?2}，其最大连续子序列为 { 11 , ? 4 , 13 } \{11,?4,13\} {11,?4,13} ，最大和为$20$。

编写程序得到其中最大子序列的和并输出该子序列的第一个和最后一个元素的下标。

输入格式

输入包含多组测试数据。

每组数据占 $2$ 行，第 $1$ 行给出正整数 $K$。

第$2$行给出$K$个整数$N_0,\dots ,N_{K?1}$。

输出格式

每组数据输出一行结果，包含最大子序列的和以及子序列的第一个下标$i$和最后一个元素的下标$j$。

所有元素下标为 $0～K?1$。

如果最大子序列不唯一，则选择$i$ 最小的那个子序列，如果仍不唯一，则选择$i$最小的子序列中$j$最小的那个子序列。

若所有$K$个元素都是负数，则定义其最大和为$0$，输出0 0 0。

数据范围

$1\le K\le 10^5$，$?10000\le N_i\le 10000$，输入最多包含$10$ 组数据。

输入样例

8
6 -2 11 -4 13 -5 -2 10
5
10 -10 10 -10 10
8
-1 -5 -2 3 -1 0 -2 0
4 
-1 -2 -4 -3

输出样例

27 0 7
10 0 0
3 3 3
0 0 0

算法思想

本题除了求最大子序列的和，还要求输出该子序列的第一个和最后一个元素的下标；并且如果方案不唯一，则选择$i$最小的子序列中$j$最小的那个子序列，也就是满足条件最左边的子序列的开始和结束位置。

为了求解满足条件的方案，也就是最左边的最大子序列，可以将之前的状态表示上稍作改变，详细可以参考每周一算法：最大连续子序列的和。

状态表示

$f[i]$表示所有以$i$为左端点的连续子段和的最大值。

状态计算

从最后一步分析，按照连续子段的长度进行分类：

• 子段长度为$1$，即只包含$1$个数，此时和为$a[i]$
• 子段长度为$2$，包含$2$个数，此时和为$a[i]+a[i+1]$
• 子段长度为$3$，包含$3$个数，此时和为$a[i]+a[i+1]+a[i+2]$
• …
• 子段长度为$n?i$，包含$n?i$个数，此时和为$a[i]+a[i+1]+...+a[n?2]+a[n?1]$

$f[i]$应取应取以上情况的最大值。

根据之前的分析，第$2$项到最后一项的最大值为$f[i+1]+a[i]$。因此 f [ i ] = m a x { a [ i ] , f [ i + 1 ] + a [ i ] } f[i]=max\{a[i],f[i+1]+a[i]\} f[i]=max{a[i],f[i+1]+a[i]}

如何计算最大的子序列的开始和结束位置呢？

开始位置

由于状态$f[i]$表示所有以$i$为左端点的连续子段和的最大值，所以当一个更大的$f[i]$出现时，那么$i$位置就是最大的子序列的开始位置。不妨设连续子段和的最大值为$ans$，开始位置为$L$，当$f[i]\ge ans$时，$L=i$。

注意，这里需要判断的是$\ge$，因为和相等时，要保留最左边的连续子段。

结束位置

考虑到连续子段的结束位置可能不同，可以使用一个数组$g[i]$来维护以$i$位置开始的最大连续子段和的结束位置，即当$f[i]\ge ans$时，$R=g[i]$。

从状态转移方程 f [ i ] = m a x { a [ i ] , f [ i + 1 ] + a [ i ] } f[i]=max\{a[i],f[i+1]+a[i]\} f[i]=max{a[i],f[i+1]+a[i]}中可以发现，当$a[i]\ge f[i+1]+a[i]$时，连续子段到$i$位置结束，和相等或者更大；否则，包含$i+1$开始的最大连续子段时和会更大，即
$$g[i]=?\begin{array}{l}i，满足a[i]\ge f[i+1]+a[i]时\\ g[i+1]，满足a[i]<f[i+1]+a[i]时\end{array}$$

初始状态

由于状态$f[i]$表示所有以$i$为左端点的连续子段和的最大值，所以在状态计算时需要从右向左（从后向前）进行枚举。此时初始状态：

• $f[n]$要尽可能小，可以让$f[n]=?1e9$
• $g[n]$应该到最后一个位置结束，题目中给出的下标从$0$到$n?1$，因此$g[n]=n?1$

由于题目中要求所有元素都是负数时，则定义其最大和为$0$，输出0 0 0，因此$ans=0,L=0,R=0$。

时间复杂度

• 状态数为$n$
• 状态计算的时间复杂度为$O(1)$，总的时间复杂度为$O(n)$

代码实现

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], f[N], g[N];

int main()
{
    int n;
    while(~ scanf("%d", &n))
    {
        for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
        int ans = 0, L = 0, R = 0;
        f[n] = -1e9, g[n] = n - 1;
        for(int i = n - 1; i >= 0; i --)
        {
            if(a[i] >= f[i + 1] + a[i])
            {
                f[i] = a[i];
                g[i] = i;
            }
            else 
            {
                f[i] = f[i + 1] + a[i];
                g[i] = g[i + 1];
            }
            if(f[i] >= ans) 
            {
                ans = f[i];
                L = i, R = g[i];
            }
        }
        printf("%d %d %d\n", ans, L, R);
    }
}

空间优化

根据状态转移方程， f [ i ] = m a x { a [ i ] , f [ i + 1 ] + a [ i ] } f[i]=max\{a[i],f[i+1]+a[i]\} f[i]=max{a[i],f[i+1]+a[i]}，可以发现$f[i]$只与$f[i+1]$相关，因此不需要用数组存储所有状态，只用一个变量滚动存储即可；$g[]$数组同理。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];

int main()
{
    int n;
    while(~ scanf("%d", &n))
    {
        for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
        int ans = 0, L = 0, R = 0;
        int f = -1e9, g = n - 1;
        for(int i = n - 1; i >= 0; i --)
        {
            if(a[i] >= f + a[i])
            {
                f = a[i];
                g = i;
            }
            else 
            {
                f = f + a[i];
                //g不变
            }
            if(f >= ans) 
            {
                ans = f;
                L = i, R = g;
            }
        }
        printf("%d %d %d\n", ans, L, R);
    }
}