首页 > 其他分享 >子段和问题

子段和问题

时间:2024-07-31 22:39:29浏览次数:13  
标签:子段 int max 问题 ans 序列 dp

Abstract

本文主要介绍各种序列子段和问题。


P1 最大子段和

传送门

Introduction

首先来看一道经典例题,求一段序列的最大子段和

Idea

考虑动态规划,令 dp[i] 表示在取第 i 个数的情况下,前 i 个数所能得到的最大子段和,那么显然有 dp[i] = max( dp[i-1] + a[i] , a[i]),其中 a[i] 表示序列的第 i 个数。

Code

#include <bits/stdc++.h>
using namespace std;

int dp[300000];
int ans = -INT_MAX;
int main()
{
    int n;
    cin >> n;
    memset(dp, -0x3f3f3f, sizeof dp);
    for (int i = 1; i < n + 1; i++)
    {
        int m;
        cin >> m; 
        dp[i] = max(dp[i - 1] + m, m);
        ans = max(ans, dp[i]); // 注意答案每次都要更新
    }
    cout << ans;
    return 0;
}

P2 双子序列最大和

传送门

Introduction

再看一道升级版的,这次我们需要找出两个不重叠的子段,使他们的各自的子段和之和达到最大值。

Idea

一个显然的想法是,我们可以依次枚举序列中的每一项,然后分别找出这一项右侧和左侧的最大子段和,然后将他们相加即可。这样一来,问题就变得和 P1 极其相似了。

我们不妨以 l[i] 表示第 i 项左边的数可以得到的最大子段和,r[i] 表示第 i 项右边的数可以得到的最大子段和,答案就是 max( l[i] + r[i] ), i = 2,3...n-1。

下面考虑如何计算 l[i] 和 r[i] , 和 P1 类似的,我们可以写出以下转移方程 l[i] = max( l[i-1] + a[i-1], a[i-1]), r[i] = max ( r[i+1] + a[i+1] , a[i+1]),这样一来,我们就成功得到了选取第 i-1/i+1 个数时,第 i 个数左侧/右侧的数所能取得的最大子段和,然后,我们对 l,r 数组做以下处理:l[i] = max( l[i] , l[i-1] ),r[i] = max( r[i] , r[i+1] ),这样一来,就将 l,r 数组转变为我们需要的东西了。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1100000;
int l[maxn];
int r[maxn];
int a[maxn];

signed main()
{
    int n;
    scanf("%lld", &n);
    memset(l, -0x3f3f3f3f, sizeof l);
    memset(r, -0x3f3f3f3f, sizeof r);
    l[1] = l[0] = 0;
    r[n] = r[n + 1] = 0;
    scanf("%lld ", &a[1]);
    for (int i = 2; i < n + 1; i++)
    {
        scanf("%lld", &a[i]);
        l[i] = max(l[i - 1] + a[i - 1], a[i - 1]);
    }

    for (int i = n - 1; i > 0; i--)
    {
        r[i] = max(r[i + 1] + a[i + 1], a[i + 1]);
    }

    for (int i = n - 1; i > 0; i--)
    {
        r[i - 1] = max(r[i - 1], r[i]);
    }

    for (int i = 2; i < n + 1; i++)
    {
        l[i + 1] = max(l[i + 1], l[i]);
    }

    int ans = -0x3f3f3f3f;
    for (int i = 2; i < n; i++)
    {
        ans = max(l[i] + r[i], ans);
    }
    cout << ans;
    return 0;
}

P3 环状最大两段子段和

传送门

Introduction

这一题是 P2 的进阶版本,怎样在环形序列中找到子段和最大的两端不重叠序列呢?

Idea

实际上,可能的情况只有两种(0表示不选,@表示选):

  1. 000@@@000@@@000
  2. @@@000@@@000@@@

第一种情况和 P2 是完全一致的,第二种情况看似有些变化,但仔细一想,选出和最大的 @ 和选出和最小的 0 好像是等价的啊!那么我们只需要把序列中的数全部都取相反数,然后再重复 P2 的操作就可以了,此题得解。

Code

#include <bits/stdc++.h>
using namespace std;

int n;
int a[300000];
int dp_l[300000];
int dp_r[300000];
int sum;
bool ok;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n + 1; i++)
    {
        scanf("%d", a + i);
        if (a[i] > 0)
        {
            ok = 1;
        }
        sum += a[i];
    }
    // 如果全是负数的话,我们只需要把最大的两个负数之和输出就可以了
    // 我不知道为啥程序会在这地方出问题所以加了特判qwq
    if (!ok)
    {
        sort(a + 1, a + 1 + n);
        cout << a[n] + a[n - 1] << endl;
        return 0;
    }

    // 阶段一
    for (int i = 1; i <= n; i++)
    {
        dp_l[i] = max(dp_l[i - 1] + a[i], a[i]);
    }
    for (int j = n; j > 0; j--)
    {
        dp_r[j] = max(dp_r[j + 1] + a[j], a[j]);
    }
    // 阶段二
    for (int i = 1; i <= n; i++)
    {
        dp_l[i] = max(dp_l[i], dp_l[i - 1]);
    }
    for (int i = 1; i <= n; i++)
    {
        dp_r[i] = max(dp_r[i], dp_r[i + 1]);
    }
    // 更新答案
    int ans1 = -INT_MAX;
    for (int i = 2; i <= n; i++)
    {
        ans1 = max(ans1, dp_l[i - 1] + dp_r[i]);
    }

    // 全部取反
    for (int i = 1; i <= n; i++)
    {
        a[i] *= -1;
    }
    // 阶段一
    for (int i = 1; i <= n; i++)
    {
        dp_l[i] = max(dp_l[i - 1] + a[i], a[i]);
    }
    for (int j = n; j > 0; j--)
    {
        dp_r[j] = max(dp_r[j + 1] + a[j], a[j]);
    }
    // 阶段二
    for (int i = 1; i <= n; i++)
    {
        dp_l[i] = max(dp_l[i], dp_l[i - 1]);
    }
    for (int i = 1; i <= n; i++)
    {
        dp_r[i] = max(dp_r[i], dp_r[i + 1]);
    }
    int ans2 = -INT_MAX;
    for (int i = 2; i <= n; i++)
    {
        ans2 = max(ans2, dp_l[i - 1] + dp_r[i]);
    }
    // 把 ans2 变换为我们需要的东西
    ans2 *= -1;
    ans2 = sum - ans2;

    // 输出 ans1,ans2 中较大的
    cout << max(ans1, ans2);
    return 0;
}

标签:子段,int,max,问题,ans,序列,dp
From: https://www.cnblogs.com/carboxylBase/p/18335654

相关文章

  • Dependency Injection: 如何解决依赖注入失败问题
    DependencyInjection:如何解决依赖注入失败问题......
  • 暗区突围pc端下载失败/卡正在初始化/连接伺服务器失败/问题解决方法
    暗区突围pc端下载失败/卡正在初始化/连接伺服务器失败/问题解决方法暗区突围pc端下载失败/卡正在初始化/连接伺服务器失败/问题解决方法暗区突围也可以在电脑上游玩拉,暗区突围PC端上线在即,本次上线就是全球抢先测试了,很多小伙伴在游戏下载过程中遇到了很多问题,比如:下载失......
  • 【MySQL】事务 【上】{事务的版本支持 事务提交方式 实验结论 用户问题 如何理解隔离
    文章目录1.引入事务事务的版本支持事务提交方式实验结论用户问题2.隔离性如何理解隔离性隔离级别查看与设置隔离性4.四种隔离级别的场景读未提交读已提交可重复读串行化1.引入事务当客户端A检查还有一张票时,将票卖掉,还没有执行更新数据库的时候,客户端B检查了票数......
  • 微信小程序分包问题1——如何分包
    为什么要分包:在开发小程序中,我上传体验版代码时,发现项目总体积过大,上传不上去,因此需要做分包处理。1.什么是分包分包指的是把一个完整的小程序项目,按照需求划分为不同的子包,在构建时打包成不同的分包,用户在使用时按需进行加载。2.分包的好处对小程序进行分包的好处主要有以下两......
  • Oracle VM VirtualBox创建虚拟机相关问题
    这次直接使用virtualbox来进行虚拟机的创建和运行。在控制项里新建一台虚拟电脑,然后就是正常的选择虚拟镜像以及设置账户密码。我正常的就给虚拟机分配4G内存,处理器4CPU,然后磁盘空间分配个16G,当然后续都是可以进行调整的。之后就是系统的安装时间了,一段不算短的等待过后,终于出现......
  • 记一次 JUnit5 问题排查(不识别单测、mock 对象空指针等问题)
    背景最近开始使用JUnit5写单元测试,本地运行成功之后提交代码,触发流水线进进行覆盖率计算。结果出来之后傻眼了,几百个单侧只能识别到2个。先简单说一下具体的环境。本地使用IDEA自带的maven,版本为3.9.6,JUnit版本5.7.0。流水线使用jenkins触发maven命令,用的maven......
  • 数组加密问题例题day05
    importjava.util.Scanner;/* 某个公司采用公用电话传递数据信息,数据是小于8位的整数,为了确保安全,在传递过程中需要加密,加密规则如下:首先将数据倒序,然后将每位数字都加上5,再用和除以10的余数代替该数字,最后将第一位和最后一位数字交换......
  • 【杂谈】JPA乐观锁改悲观锁遇到的一些问题与思考
    背景接过一个外包的项目,该项目使用JPA作为ORM。项目中有多个entity带有@version字段当并发高的时候经常报乐观锁错误OptimisticLocingFailureException原理知识JPA的@version是通过在SQL语句上做手脚来实现乐观锁的UPDATEtable_nameSETupdated_column=new_value,vers......
  • Multipass相关问题
    最近又想把Multipass翻出来玩玩,结果一直会有一个报错:由于很久没有打开过了,所以我决定用geek进行完全卸载后重装。照例,先进行multipass数据目录的配置:Set-ItemProperty-Path"HKLM:System\CurrentControlSet\Control\SessionManager\Environment"-NameMULTIPASS_STORAGE-V......
  • 使用 chatgpt 从采访脚本中提取问题和答案
    我的要求是从面试脚本中提取问题和答案,并基于Skill.csv文件中给出的技能列表。我创建了生成人工智能模型来从给定的技能列表中提取问题和答案。但它只给出了30%正确的问题和答案以及技能标签。请找到我的下面的代码并执行需要的操作。我的输入是csv文件,其中有一列包含“pyh......