9.动态规划——2.最大序列和

例题——最大序列和

在这里插入图片描述

找状态

思路一(×)

定义一个状态 d p [ i ] dp[i] dp[i],计为前i个数构成子序列和的最大值
此法状态转移比较困难,即若 d p [ i ] dp[i] dp[i] d p [ i − 1 ] dp[i-1] dp[i1]没有明确的关系,有可能两个子序列和取在不同的连续子串上

思路二(√)

同样定义一个状态 d p [ i ] dp[i] dp[i],计为前i个数构成子序列和的最大值,但与思路一不同的是,这次的 d p [ i ] dp[i] dp[i]中必须包含序列中最后一个结点(即前i个结点中第i个结点),从而能够构建 d p [ i ] dp[i] dp[i] d p [ i − 1 ] dp[i-1] dp[i1]的关系
破题绝招:假设已知 d p [ i ] dp[i] dp[i](包含最后一个结点),那么:

  • d p [ i ] dp[i] dp[i]就是最大子序和时,有a[i]>0且a[i+1]<0
  • d p [ i ] > = 0 dp[i]>=0 dp[i]>=0时,必有: d p [ i + 1 ] = a [ i + 1 ] + d p [ i ] dp[i+1]=a[i+1]+dp[i] dp[i+1]=a[i+1]+dp[i]
  • d p [ i ] < 0 dp[i]<0 dp[i]<0时,必有: d p [ i + 1 ] = a [ i + 1 ] dp[i+1]=a[i+1] dp[i+1]=a[i+1]

当我们求出所有的 d p [ i ] dp[i] dp[i],求最大值即可

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <climits>
//#include <bits/stdc++.h>
using namespace std;
long long a[1000001];
long long dp[1000001];
long long max_subsequence(int n){long long maximum = LONG_LONG_MIN;for (int i = 0; i < n; ++i) {if (i==0){dp[i] = a[i];} else{dp[i] = max(a[i],a[i]+dp[i-1]);}maximum = max(maximum,dp[i]);}return maximum;
}int main() {int n;while(scanf("%d",&n)!=EOF){for (int i = 0; i < n; ++i) {scanf("%lld",&a[i]);}printf("%lld\n", max_subsequence(n));}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/293062.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Ribbon有哪些负载均衡策略

负载均衡类都实现了IRule接口。 RandomRule&#xff1a;随机的选用一个实例 RoundRobinRule&#xff1a;轮询的使用实例 RetryRule&#xff1a;在轮询的基础上加了一个错误重试机制&#xff0c;在deadline时间内会不断的重试 WeightResponeTimeRule&#xff1a;根据权重去做…

【计算机网络】四层负载均衡和七层负载均衡

前言 1、分层方式 首先我们知道&#xff0c;在计算机网络中&#xff0c;常用的协议分层方式&#xff1a;OSI和TCP/IP&#xff0c;以及实际生产中使用的协议划分方式。 在OSI中&#xff0c;各层的职责如下&#xff1a; 应用层&#xff1a;对软件提供接口以使程序能使用网络服…

深入探索位图技术:原理及应用

文章目录 一、引言二、位图&#xff08;Bitset&#xff09;基础知识1、位图的概念2、位图的表示3、位图操作 三、位图的应用场景1、数据查找与存储2、数据去重与排序 四、位图的实现 一、引言 位图&#xff0c;以其高效、简洁的特性在数据处理、存储和检索等多个领域发挥着举足…

Nest安装及使用~

前提条件 请确保您的操作系统上安装了 Node.js&#xff08;版本 > 16&#xff09; &#x1f4da;要查看指南&#xff0c;请访问 https://docs.nestjs.com/ &#x1f4da;要查看中文 指南&#xff0c; 请访问 https://docs.nestjs.cn/ $ node -v v16.18.1 $ npm -v 7.x.x安…

【C++】C++11的新特性

目录 一. 列表初始化1. 列表初始化的原理: initializer_list 二. 类型的声明1. auto2. decltype 三. nullptr四. 范围 for五. STL容器变化六. 类的新功能 一. 列表初始化 在 C 语言中, 就可以使用 {} 对数组或结构体进行初始化, 而 C11 扩大了 {} 的使用范围, 使其可以初始化所…

Mysql-数据库范式和Mysql安装

文章目录 数据库三范式第一范式&#xff1a;1NF第二范式&#xff1a;2NF第三范式&#xff1a;3NF Yum安装CentOS7 yum安装解决“Access denied”拒绝访问异常 数据库三范式 第一范式&#xff1a;1NF 第一范式&#xff1a;数据库中无重复的列&#xff0c;每一列都是不可分割的…

乐乐音乐鸿蒙版-支持krc歌词(动感歌词、翻译和音译歌词)

简介 乐乐音乐主要是基于HarmonyOS开发的音乐播放器&#xff0c;它支持lrc歌词和动感歌词(ksc歌词、krc歌词和hrc歌词等)、多种格式歌词转换器及制作动感歌词、翻译歌词和音译歌词。 开发环境 ArkTS、Stage模型、SDK3.1、 API 9 注&#xff1a;没试过在真机条件下调试。 功…

Java基础学习: JDK动态代理

文章目录 一、什么是JDK动态代理二、JDK动态代理的特点三、JDK动态代理类如何使用四、JDK动态代理原理分析1、创建代理对象2、生成代理类 一、什么是JDK动态代理 JDK动态代理是Java提供的一种动态生成代理类和代理对象的技术。它主要利用Java的反射机制实现&#xff0c;在运行…

Open CASCADE学习|GeomFill_Frenet

GeomFill_Frenet继承自GeomFill_TrihedronLaw类。GeomFill_Frenet类主要用于实现Frenet标架的计算。Frenet标架是一个沿曲线移动的局部坐标系&#xff0c;它由切向量、法向量和副法向量组成&#xff0c;常用于机器人学、计算机图形学等领域。 class GeomFill_Frenet : publi…

docker 数据卷

Docker数据卷是Docker中的一个核心机制&#xff0c;用于实现容器间数据的持久化和共享。它是宿主机上的一个特殊目录&#xff0c;可以供一个或多个容器使用。容器删除时&#xff0c;不会删除其挂载的数据卷&#xff0c;也不会存在类似的垃圾机制对容器存在的数据卷进行处理。 …

每日面经分享(Spring Boot: part2 DAO层)

1. Spring Boot DAO层的作用 a. 封装数据访问逻辑&#xff1a;DAO层的主要责任是封装与数据访问相关的逻辑。负责处理与数据库的交互&#xff0c;包括数据的增删改查等操作。通过将数据访问逻辑统一封装在DAO层中&#xff0c;可以提高代码的可维护性和可重用性。 b. 解耦业务逻…

【vue3学习笔记(二)】(第141-143节)初识setup;ref函数_处理基本类型;ref函数_处理对象类型

尚硅谷Vue2.0Vue3.0全套教程丨vuejs从入门到精通 本篇内容对应课程第141-143节 课程 P141节 《初识setup》笔记 1、setup是所有组合式API“表演的舞台”&#xff0c;组件中所用到的所有数据、方法、监视数据、生命周期钩子等都需要配置在setup中。 2、setup的两种返回值&…

【Linux】socket套接字

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;折纸花满衣 &#x1f3e0;个人专栏&#xff1a;题目解析 目录 &#x1f449;&#x1f3fb;IP地址和端口号pid和port的关系 &#x1f449;&#x1f3fb;TCP和UDP&#x1f449;&#x1f3fb;网络字节序&…

NineData与StarRocks商业化运营公司镜舟科技完成产品兼容认证

近日&#xff0c;镜舟科技与NineData完成产品兼容测试。在经过联合测试后&#xff0c;镜舟科技旗下产品与NineData云原生智能数据管理平台完全兼容&#xff0c;整体运行高效稳定。 镜舟科技致力于帮助中国企业构建卓越的数据分析系统&#xff0c;打造独具竞争力的“数据护城河”…

2-HDFS常用命令及上传下载流程

HDFS NameNode 安全模式(safemode) 当NameNode被重启的时候&#xff0c;自动进入安全模式 在安全模式中&#xff0c;NameNode首先会触发edits_inprogress文件的滚动。滚动完成之后&#xff0c;更新fsimage文件 更新完成之后&#xff0c;NameNode会将fsimage文件中的元数据加…

STM32——超声测距HC_SR04记录

一、HC_SR04简述 HC-SR04超声波测距模块可提供 2cm-400cm的非接触式距离感测功能&#xff0c;测距精度可达高到 3mm&#xff1b;模块包括超声波发射器、接收器与控制电路。 基本工作原理&#xff1a; (1)采用IO 口TRIG 触发测距&#xff0c;给最少10us 的高电平信呈。 (2)模块…

一文教你轻松领取华为云优惠券

随着云计算技术的快速发展&#xff0c;越来越多的企业和个人选择使用云服务来满足他们的需求。华为云作为全球领先的云服务提供商之一&#xff0c;为用户提供了丰富的产品和服务。为了帮助用户更好地体验华为云服务&#xff0c;本文将为大家详细介绍如何轻松领取华为云优惠券。…

Taskflow:限制最大并发度( Limit the Maximum Concurrency)

定义信号量Semaphore Taskflow提供了一个机制&#xff0c;tf::Semaphore&#xff0c;用于限制任务部分中的最大并发。您可以让任务在执行工作之前/之后获取/释放一个或多个信号量。一项任务可以获取和释放信号量&#xff0c;或者只是获取或只是释放它。tf::Semaphore对象以初始…

MySQL介绍

1 什么是Mysql MySQL是一个开源的关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;它使用结构化查询语言&#xff08;SQL&#xff09;进行数据库管理。自上世纪90年代中期以来&#xff0c;MySQL凭借其易用性、稳定性和高效性能&#xff0c;赢得了广泛的用户群体…

政安晨:【Keras机器学习实践要点】(三)—— 编写组件与训练数据

目录 介绍 编写组件 训练模型 政安晨的个人主页&#xff1a;政安晨 欢迎 &#x1f44d;点赞✍评论⭐收藏 收录专栏: TensorFlow与Keras机器学习实战 希望政安晨的博客能够对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff01; 介绍 通过 Ker…