当前位置: 首页 > article >正文

C++算法入门练习——最大连续子序列和

现有一个整数序列a1,a2,...,an​​​,求连续子序列ai...aj,使得ai+...+aj​​​最大。

输出三个整数,分别表示最大连续子序列和、满足该最大和的连续子序列和的首尾元素的下标i、j​。

如果有多种满足条件的最优方案,那么输出首元素下标i最小的方案;如果还有多解,那么输出尾元素下标j最小的方案。

解题思路:

利用动态规划思想,当我们遇见一个新的元素后,我们只有两种状态选择:

①将这个元素与上一个进行拼接

②这个元素自己单独成为一个新的连续子序列和的开始。

而选择1还是2的条件为:上一个元素的dp数组是否大于等于0。如何理解这个条件呢?如果大于等于0,那么我们新加入元素,如果是正的,就能够使得这个连续子序列和变得更长,而如果是负的,并且负的程度远大于前面的,那么下一个元素,就会自立起新的门户,而上一个的dp值已经是暂时的最大值,如果负的程度比较小,说明可以接受,因为可以通过吸收更多正值来缓解这一个负值。

而为了记录序列开始的首下标,我们要用一个start数组进行回溯,去保存父亲结点,类似于并查集。

完整代码如下:

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int n;
	cin>>n;
	int dp[n];
	int data[n];
	for(int i=0;i<n;i++){
		cin>>data[i];
	}
	dp[0] = data[0];
	int start[n];
	start[0] = 0;
	for(int i=1;i<n;i++){
		if(dp[i-1]>=0){
			dp[i] = dp[i-1]+data[i];
			start[i] = start[i-1];
		}
		else{
			dp[i] = data[i];
			start[i] = i;
		}
	}
	int k = 0;
	for(int i=1;i<n;i++){
		if(dp[k]<dp[i]){
			k = i;
		}
	}
	cout<<dp[k]<<" "<<start[k]+1<<" "<<k+1<<endl;
	return 0;
}


http://www.kler.cn/a/157440.html

相关文章:

  • BGP的六种状态分别是什么?
  • uniapp开发app,cover-view不能隐藏,使用v-if,v-show都不行的解决办法
  • 大数据机器学习算法和计算机视觉应用07:机器学习
  • 杂七杂八的网络安全知识
  • 【原生js案例】让你的移动页面实现自定义的上拉加载和下拉刷新
  • 【Rust自学】4.4. 引用与借用
  • vue2+electron桌面端一体机应用
  • golang实现函数yamlToStruct(infile,outFile)
  • 如何拆解Unity 2022.3版本的AssetBundle
  • GB/T 29734.1-2013 铝木复合门窗检测
  • 基于SSM的老年公寓信息管理的设计与实现
  • python提取通话记录中的时间信息
  • 翻译: 生成式人工智能的工作原理How Generative AI works
  • 如何使用Cloudreve搭建本地云盘系统并实现随时远程访问
  • VSCode搭建STM32开发环境
  • LLM之Agent(三):HuggingGPT根据用户需求自动调用Huggingface合适的模型
  • 数据库系统概论期末经典大题讲解(用关系代数进行查询)
  • 前端 --- HTML
  • 【设计模式-4.3】行为型——责任链模式
  • Hive安装与配置
  • webpack打包体积优化,减少白屏时间
  • ARM与大模型,狭路相逢
  • 探索人工智能领域——每日20个名词详解【day6】
  • 关于近期互联网行业收缩的一些看法
  • 关于rocketMQ踩坑的那些事
  • 【hacker送书第8期】Java从入门到精通(第7版)