P1115 最大子段和-Toy模板网

这篇具有很好参考价值的文章主要介绍了P1115 最大子段和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n。

第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ai。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1复制

7
2 -4 3 -1 2 -4 3

输出

说明/提示

样例 1 解释

选取 [3,5]子段 {3,−1,2}，其和为 4。

法一:线性DP:

定义状态:

首先:先分析一下情况

由于我们想求最大值并且是截取一个子段那么一个数能否被纳入这个子段取决于它的贡献是否为正贡献,也就是说我们希望纳入子段的数是一个正数。

而能影响一个数是否能提供一个正贡献,一个因数是其本身的值,一个因数是它的前一个值能否带动它提供一个正数,例如-1本身是一个负贡献,如果它的前值为10,由于它的前值正贡献大于其本身的负贡献,我们也将其纳入其中.

由此定义DP[i]以i结尾的最大贡献

取 num[i] 的情况:

取 i : num[i]为正数

num[i]为负 ,num[i - 1]的正贡献大于num[i]的负值

    for(int i = 1;i <= n;i++)
    dp[i] = max(a[i],num[i] + dp[i - 1]);

线性DP == AC 代码

#include<bits/stdc++.h>
#define int i64
using i64 = int64_t;
using namespace std;
const int maxn = 2e5 + 10;
int dp[maxn];
int n, num[maxn];
int ans = -1e6;
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    cin >> num[i];
    for(int i = 1;i <= n;i++)
    {
       dp[i] = max(num[i],num[i] + dp[i - 1]);
       ans = max(ans,dp[i]);
    }
    cout << ans << endl;
    return 0;
}

解法二:在线处理(数据结构中最基础的算法)

#include<bits/stdc++.h>
#define int i64
using i64 = int64_t;
using namespace std;
const int maxn = 2e5 + 10;
int n,sum, num[maxn];
int ans = -1e6;
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    cin >> num[i];
    for(int i = 1;i <= n;i++)
    {
        if(sum < 0)sum = num[i];
        else sum += num[i];
        ans = max(ans,sum);
    }
    cout << ans << endl;
    return 0;
}

解法三:前缀和

我们知道前缀和是存储前i个和的值,那么对于最大子序列[i , j]的值就是前缀和中的s[j] - s[i - 1]

如果我们想让子序列和为最大,则我们希望s[j]尽可能大,以及s[i - 1]尽可能小,对于s[j]通过枚举每一个选项即可,那么最终取决于找到最小的s[i - 1]以及当前j的位置文章来源地址https://www.toymoban.com/news/detail-484400.html

#include<bits/stdc++.h>
#define int i64
using i64 = int64_t;
using namespace std;
const int maxn = 2e5 + 10;
int n,sum, num[maxn],s[maxn],m;
int ans = -1e6;
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
       cin >> num[i];
       s[i] = num[i] + s[i - 1];
    }
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans,s[i] - m);
        m = min(m,s[i]);
    }
    cout << ans << endl;
    return 0;
}

到了这里，关于P1115 最大子段和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！