首页 > 其他分享 >最大子列和问题

最大子列和问题

时间:2023-06-13 22:13:05浏览次数:20  
标签:ch 子列 sum long 问题 define ans include 最大

最大子列和问题

分为两种类型:①不限制子序列的长度、②限制子序列的长度

问题一:不限制子序列的长度

题:Max Sum
解法一:贪心法,从前向后遍历序列,统计当前和,若当前和大于已有ans,则更新已有答案;若当前和小于0,则由贪心的思想,令当前和为零从新开始统计
下见代码:

//>>>Qiansui
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<string>
#include<vector>
#include<utility>
#include<iomanip>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
//#define int long long

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
	return x*f;
}

using namespace std;
const int maxm=1e6+5,inf=0x3f3f3f3f,mod=998244353;
ll n;

void solve(){
	int c;
	cin>>c;
	ll t,sum,ans=0,pa,pb,f;
	for(int i=1;i<=c;++i){
		cin>>n;
		f=pa=pb=1;
		ans=-1000-5;
		sum=0;
		for(int j=1;j<=n;++j){
			cin>>t;
			sum+=t;
			if(sum>ans){
				ans=sum;
				pb=j;
				pa=f;
			}
			if(sum<0){
				sum=0;
				f=j+1;
			}
		}
		cout<<"Case "<<i<<":\n";
		cout<<ans<<' '<<pa<<' '<<pb<<'\n';
		if(i<c) cout<<'\n';
	}
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
//	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

问题二:限制子序列的长度

标签:ch,子列,sum,long,问题,define,ans,include,最大
From: https://www.cnblogs.com/Qiansui/p/17478816.html

相关文章

  • 【VRP问题】基于遗传算法求解多约束多无人机灾情应急救援路径规划问题附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • Niushop的PC端404出问题
    路径错误的话,看图,如果是网页正常打开,但是刷新就出错,那么配置文件没配置好 location/web{try_files$uri$uri/web//web/index.html;}   ......
  • 【解决一个小问题】golang 的 `-race`选项导致 unsafe代码 panic
    作者:张富春(ahfuzhang),转载时请注明作者和引用链接,谢谢!cnblogs博客zhihuGithub公众号:一本正经的瞎扯为了提升性能,使用unsafe代码来重构了凯撒加密的代码。代码如下:const( lowerCaseAlphabet="abcdefghijklmnopqrstuvwxyz" upperCaseAlphabet="ABCDEFGHIJKLMN......
  • FFmpeg服务器适配问题
    用org.bytedeco  javacv/ ffmpeg-platform  /javacpp 实现的ffmpeg视频抽帧截取图片在cenos正常但是在arm64服务器有适配的问题。解决方案换另外的实现: <groupId>ws.schild</groupId>      <artifactId>jave-all-deps</artifactId>      ......
  • MySQL字符索引没用上问题
    某一天,接口突然502,运维同学说没有可用的PHP进程了,看监控说是这个接口夯住了,导致请求进不来,临时把这个接口给返回了200(PS:线上这个接口没有实际作用,所以这么操作了);给了慢查询的SQL,用explain看了下,发现竟然没有用到创建的索引,此时数据库的量有大概150万行,对SQL里where字段加了双引......
  • ORACLE常见问题一千问(提供下载)(不怕学不成、就怕心不诚!)
    ORACLE常见问题一千问(提供下载)(不怕学不成、就怕心不诚!)——通过知识共享树立个人品牌。ORACLE常见问题是我收集完成,在此共享出来,一为自己以后好做个参考,二为需要的朋友提供帮助。同时,感谢提供这些相关问题及解决方法的朋友。欢迎大家补充,交流与分享才能共同进步嘛,感谢!后附电子版下......
  • 1792.最大平均通过率
    问题描述1792.最大平均通过率(Medium)一所学校里有一些班级,每个班级里有一些学生,现在每个班都会进行一场期末考试。给你一个二维数组classes,其中classes[i]=[passᵢ,totalᵢ],表示你提前知道了第i个班级总共有totalᵢ个学生,其中只有passᵢ个学生可以通过考试。给......
  • 1798.你能构造出连续值的最大数目
    问题描述1798.你能构造出连续值的最大数目解题思路贪心+动态规划首先将数组按升序排序,令res[n]为前n个数所能构造出的连续整数的最大值:if(coins[i-1]>res[n-1]+1),res[n]=res[n-1]+coins[i-1];else,res[n]=res[n-1];代码classSolution{publi......
  • 1710.卡车上的最大单元数
    问题描述1710.卡车上的最大单元数解题思路根据每个箱子可以装载的单元数量从大到小对boxTypes排序,然后每次将单元数量最大的箱子填入卡车。使用快速选择算法可以将时间复杂度降低到$O(n)$。代码classSolution{public:intmaximumUnits(vector<vector<int>>&boxTy......
  • 84. 柱状图中最大的矩形
    给定n个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为1。求在该柱状图中,能够勾勒出来的矩形的最大面积。示例1:输入:heights=[2,1,5,6,2,3]输出:10解释:最大的矩形为图中红色区域,面积为10首先单调栈首先要确定左右的范围因为画矩形时,要找到......