专栏首页ypw最大连续子序列和(最大子数组和)四种最详细的解法

最大连续子序列和(最大子数组和)四种最详细的解法

问题描述:给一个数组,有正有负,求其连续子序列的最大值

解法1:穷举暴力法 枚举左端点跟右端点,然后遍历更新所有的子序列和,最终得到结果就是最大的

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5+10;
int a[N],b[N]; 
int n ;
int ans ;
const int INF = 0x3f3f3f;  
int main()
{
	int n;
	cout<<"please input size"<<endl;
	cin>>n;
	cout<<"please input data"<<endl;
	for(int i =1;i<=n;++i)
	{
		cin>>a[i];
	}
    int ans = -INF;
    for(int i =1;i<=n;++i)
    {
        for(int j =i;j<=n;++j)
        {
        	
            int sum = 0;
  
            for(int k=i;k<=j;++k)
            {
                sum+=a[k];
            }
    
            ans = max(ans,sum);
        }

    }

    cout<<ans<<endl;
    return 0;
   
}

解法2:单调队列求解

思路:维护一个单调递增的前缀和队列,队首元素是整个序列的最小值,维护队列的同时,用前缀和的元素减去这个最小值,得到值最大,为这数组的子序列的最大值

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5+10;
int a[N],b[N]; 
int n ;
int ans ;
const int INF = 0x3f3f3f; 
deque<int> q;
int main()
{
	int n;
	cout<<"please input size"<<endl;
	cin>>n;
	cout<<"please input data"<<endl;
	for(int i =1;i<=n;++i)
	{
		cin>>a[i];
	}
	q.push_back(0),b[0] = 0;
	for(int i =1;i<=n;++i)
	{
		b[i] = b[i-1]+a[i];
		
		ans = max(ans,b[i]-b[q.front()]);
		
		while(!q.empty()&&b[i]<=b[q.back()])
			q.pop_back();
		q.push_back(i);
	}
	cout<<ans<<endl;
    return 0;
   
}

解法3:分治法 思路:分三种情况讨论 1.计算left到k的和的和,记作left_sum; 2.计算k+1到right的和,记作right_sum; 3.跨边界和,以k为中心向两边分别求和 1.从中心向左扩张一步,记录当前sum1,并于上一步对比, 若大于,则更新left 2.从中心向右扩张一步,记录当前sum2,并于上一步对比, 若大于,则更新right 3.计算连续字段和 sum = sum1+sum2; 计算完后,取三者最大值

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5+10;
int a[N],b[N], dp[N];;
int n ;
int ans ;
const int INF = 0x3f3f3f; 

int solve4(int l,int r)
{
	if(l==r)
		return a[l];
	int mid = (l+r)>>1;
	int left_sum = solve4(l,mid);
	int right_sum = solve4(mid+1,r);
	int sum1=0,sum2=0,s1=0,s2=0;
	//閿熸枻鎷烽敓绔枻鎷烽敓锟?
	for(int i =mid;i>=l;--i)
	{
		s1+=a[i];
		sum1=max(sum1,s1);
	}
	for(int i =mid+1;i<=r;++i)
	{
		s2 +=a[i];
		sum2 = max(sum2,s2);
	}
	int sum = sum1+sum2;

	return max(max(left_sum,right_sum),sum);
}

int main()
{
	int n;
	cout<<"please input size"<<endl;
	cin>>n;
	cout<<"please input data"<<endl;
	for(int i =1;i<=n;++i)
	{
		cin>>a[i];
	}
   
	int ans = solve4(1,n);
	cout<<ans<<endl;
	 system("pause");
    return 0;
   
}

4.动态规划 思路:这已经是可以用动态规划思想去考虑的最简单的问题了, 每一步的决策无非就是,是否继续把下一个元素加入当前的子段. 动态规划大显身手。我们开一个数组dp[] , 记录dp[i]表示以a[i]结尾的 全部子段中 最大的那个的 和。 这样我们就可以根据它dp[i] 的正负,去考虑是否把下一个元素加入到当前的子段。 如果dp[i] 是负数,那么我们为什不从a[i+1]新维护一个子段呢? 如果dp[i] 是正数,那么显然可以继续把a[i+1] 加入到当前的子段。 最后我们只需要找出所有最大子段中,最大的那个。

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5+10;
int a[N],b[N], dp[N];;
int n ;
int ans ;
const int INF = 0x3f3f3f; 

int main()
{
	int n;
	cout<<"please input size"<<endl;
	cin>>n;
	cout<<"please input data"<<endl;
	for(int i =1;i<=n;++i)
	{
		cin>>a[i];
	}
	dp[1] = a[1];
	int ans =0;
	for(int i =2;i<=n;++i)
	{
		if(dp[i-1]>0)
			dp[i] =dp[i-1] + a[i];
		else
			dp[i] = a[i];
		ans = max(ans,dp[i]);
	}
	cout<<ans<<endl;

	 system("pause");
    return 0;
   
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 口算训练 HDU - 6287

    小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为n的正整数序列a1,a2,…,an,要求小T抛出m个问题以训练他的口算能力。

    用户7727433
  • Treepath

    给定一棵n个点的树,问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。 输入描述: 第一...

    用户7727433
  • 用归并排序求逆序对数(包括归并排序算法实现及代码)

    那么我们很容易想到这个题有一种O(n*n)的暴力解法,但这不是我们所需要的,所以,要想归并排序来实现求逆序对数,那么首先我们要了解并掌握归并排序算法。

    用户7727433
  • 不引入新的数组,实现数组元素交换位置函数

             最近遇到一道C++的面试题,要求不引入新的数组,实现数组元素交换位置函数,看似挺简单的,却还是花费了我不少时间,这里记录下来,给大家一个简单的...

    用户1221057
  • ViewDragHelper使用笔记及侧滑菜单实践

    佛系编码
  • 口算训练 HDU - 6287

    小Q非常喜欢数学,但是他的口算能力非常弱。因此他找到了小T,给了小T一个长度为n的正整数序列a1,a2,…,an,要求小T抛出m个问题以训练他的口算能力。

    用户7727433
  • 风险度量

    题目 X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路,构成通信网。 两个空间站间可能直接通信,也可能通过其它空间站中转。

    用户4492257
  • L3-004. 肿瘤诊断

    在诊断肿瘤疾病时,计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域,请你计算肿瘤的体积。

    指点
  • NYOJ 116 士兵杀敌(二) (线段树+树状数组)

    题目链接:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=116

    Ch_Zaqdt
  • 浙大版《C语言程序设计(第3版)》题目集 习题6-2 使用函数求特殊a串数列和

    给定两个均不超过9的正整数a和n,要求编写函数求a+aa+aaa++⋯+aa⋯a(n个a)之和。

    C you again 的博客

扫码关注云+社区

领取腾讯云代金券