典型贪心算法 首先每个金蛋是连续的我们只能取连续的金蛋，并且要让连续相加的值最大那么有以下几种情况要进行讨论 1、如果全都是非正数的情况，那么只需要循环找到最大值即可 2、排除第一种情况那么就一定会存在大于0的数，想让结果最大那么就要尽可能多的正数相加注意，所以我选择直接找到序列的第一个正数从序列的第一个正数开始相加，满足贪心算法的思想，之后如果遇到负数又分为两种情况： （1）如果该正数加上之后的负数过后的值仍然大于0那么让他继续加因为负数后面如果还存在正数那么加上之前的值结果可能会增大，如果结果一旦增大了那么立即保存该结果并记录下坐标 （2）如果正数加上之后的负数小于等于0了那么马上停止，重新寻找第一个正数并再进行2过程

#include<stdio.h>
#include<stdlib.h> 
//贪心算法
//让尽可能多的正数相加 
int a[1000001];
struct value{
	int head;
	int tail;
    int sum;
    int max;
};
struct value val[100000];
int main(){
	int n;//金蛋数量 
	int sum = 0;
	int flag = 0;
	int j = 0;
	int k = 0;//结构体下标 
	int max_num = 0;
	int len = 0;
	int m = 0;
	scanf("%d",&n); 
	for(int i=0; i<n; i++){
	   scanf("%d",&a[i]);
	   if(a[i]>0)//如果有一个正数则不是全负 
	   flag = 1; 	
	}
	if(!flag){  //全负的情况,如果全负那么最大的奖励则是负的最小值 
	    max_num = a[0];
		for(int i=0; i<n; i++){
			if(a[i] > max_num){
				max_num = a[i];
				j = i;
			}
		}
		printf("%d\n",j+1);
		printf("%d\n",j+1);
		printf("%d\n",a[j]);
		return 0;   
	}
    else{//竟然有正数那么就先找到第一个正数,有正数就绝对不要从负数开始加 
          while(a[j]<=0)//如果前面有负数则找到第一个非负数 
            j += 1;
            val[k].sum = 0;
            val[k].max = 0;
            len++;
            //将第一个大于零的数存入到结果中 
            val[k].sum += a[j];
            val[k].max += a[j];
            val[k].head = j;
            val[k].tail = j;
            //循环遍历之后的数据 
		  	for(int i=j+1; i<n; i++){
		  	    val[k].sum += a[i];//让sum去增加 
				if(val[k].sum > val[k].max){//说明后面一个数是正数 
				   val[k].max = val[k].sum;
				   val[k].tail = i;//终止位向后移动 	
				}
				//如果sum<max说明后面一位是负数
				//注意如果后面有负数是有两种情况的
				//第一种情况就是加上后面的负数后值仍然大于0
				//那么再加上后面的正数就会增大
				//第二种情况如果加上后面的负数过后值小于0了就不要再加了 
				else{ 
					if(val[k].sum>0){
					 continue;
					}
					else{//如果加了后面的数值小于等于0了那么就重新从后面的第一个为正的数开始 
					   	while(a[i] <= 0)
					   	i++;
					   	k++;
					   	len++;
					   	val[k].sum = 0;
					   	val[k].max = 0;
					   	val[k].head = i;
					   	val[k].tail = i;
					   	val[k].sum += a[i];
					   	val[k].max += a[i];
					}
				}  	
			}
	  }
	  max_num = val[m].max;
	  for(int i=0; i<len; i++){
	  	  if(val[i].max>max_num){
	  	  	  max_num = val[i].max;
	  	  	  m = i;
		 }
	  }
	  printf("%d\n",val[m].head+1);
	  printf("%d\n",val[m].tail+1);
	  printf("%d\n",val[m].max);			
}

注意，不同情况得到的最大值都需要保存在对应的结构体数组中，之后再循环遍历结构体数组，找出最大值中的最大值以及坐标

题解

子序列最大和倒是挺好做的，关键就在那两个起始位置不容易找到，然后直接代码

代码

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int main(){
	std::ios::sync_with_stdio(false);
	int n,sum=0,ma=INT_MIN;
	cin>>n;
	int a[n+5],b=1,e=1,m=1;//m很关键哈
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
		if(ma<sum){//先进行这项，以免全部元素都是负数的时候能存进ma,
			ma=sum;
			b=m;//最大值改变，下标记得调整
			e=i;
		}
		if(sum<0){
			sum=0;
			m=i+1;//记录起始位置下标，根据第一个if来调整
			if(m==n+1) m=n;
		}
	}
	cout<<b<<endl;
	cout<<e<<endl;
	cout<<ma<<endl;
	return 0;
}

思路 子序列最大和

看到好像没人用我这方法做，多写写

我用a记录初始编号，b记录终止编号，fg用来记录是否数组数字全为负数，max记录当前数组内最大值，aa记录当前数组内最大数的位置，c来更新有效初始位置（原因下面说）maxsum记录当前算得最大奖励值，sum记录当前算得奖励值 首先将所有数读入，判断所有数是否都为负数，如果是的话就直接输出数组最大值所在位置，因为负数都越加越小

当所有数不都为负数时，设a[i]为和最大序列的起点，如果a[i]是负的，那么它不会是 和最大子序列的起点，可以得到：负的子序列也不会是 和最大子序列 的前缀。

所以在循环中用b一直更新当前 和最大子序列 的终点坐标，用a更新其起点坐标

注意：当此时子序列和为负数时起点要向后移，再继续向后找，但之前记录的可能正确起点就要先用c来储存

最后分情况输出答案即可

代码

#include<stdio.h>
int main()
{
	int a=1,b=1,n,s[100005]={0},fg=0,max=-1000000,aa,c=1;
	int maxsum = 0,sum;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s[i]);
		if(s[i]>0)fg=1;
		if(s[i]>max)max=s[i],aa=i;
	}
	for(int i=1;i<=n;i++)
	{
			sum+=s[i];
			if(sum>maxsum)
			{
				b=i;
				maxsum=sum;
				c=a;
			}
			else if(sum<0)
			{
				a=i+1;
				sum=0;
			}
	}
	if(fg==1)
	printf("%d\n%d\n%d",c,b,maxsum);
	else
	printf("%d\n%d\n%d",aa,aa,max);
        return 0;
 }

最长连续子序列和问题，我用了dp，状态转移方程是f[i] = max(f[i-1]+a[i],a[i])；但因为我实在是太弱了，没想到怎么找出两个边界，我只能又遍历了两次，等于最大值的i就是右边界，然后我从i往左找，再找左边界qaq