[NC235948] 最大子串和

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

给你一个数组 $a$ ，包含 $n$ 个整数，你需要在其中选择连续的几个（至少一个）数，使得它们的和最大，求出最大的和。

输入描述:

第一行输入一个正整数 $n(1\le n\le10^6)$ , 表示数组 $a$ 大小.

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n(-10^9\le n \le 10^9)$ , 表示数组 $a$ .

输出描述:

示例1

输入

1
2
6
1 -2 5 2 -3 5

输出

1
9

说明

1
你可以选择区间[3,6]的子串，他们的和为5+2−3+5=9。

示例2

输入

1
2
8
-3 2 -3 2 2 -1 3 -2

输出

1
6

题解

题目解析

这个题目使用的方法是动态规划(dp),其时间复杂度是$O(n)$级别.

动态规划的状态转移方程为:

解释一下,$dp[i]$的意思为以$i$位置的数字为子串结尾的最大值,其状态转移方程的解释为:以$i$位置的数字为子串结尾的最大值=$\max$(以$i-1$位置的数字为子串结尾的最大值+第$i$位置的数字,第$i$位置的数字),也就是前面的最大值加上当前值和当前值进行比较,哪个大留哪个.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 1e6+10;
long long a[MAXN],dp[MAXN];

int main(){
    long long n,ans=0;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    ans = a[0] = dp[0] = -0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        dp[i] = max(dp[i-1] + a[i],a[i]);
        ans = max(ans,dp[i]);
    }
    cout << ans;
    return 0;
}

吐槽+小技巧

真的是第一次见这种求最大值方法,记下了记下了.20号要考省赛了,好紧张.