当前位置： 首页 > news >正文

沈阳网站建设搜q479185700/企业推广方法

news 2024-12-02 13:08
沈阳网站建设搜q479185700,企业推广方法,产品设计公司介绍,温州15000 做网站的工作描述 输入一个长度为n的整数序列，从中找出一段不超过M的连续子序列，使得整个序列的和最大。例如 1，-3,5,1，-2,3当m4时，S51-237当m2或m3时，S516输入格式 第一行两个数n,m第二行有n个数，要求在n个…

描述

输入一个长度为n的整数序列，从中找出一段不超过M的连续子序列，使得整个序列的和最大。

例如 1，-3,5,1，-2,3

当m=4时，S=5+1-2+3=7
当m=2或m=3时，S=5+1=6

输入格式

第一行两个数n,m
第二行有n个数，要求在n个数找到最大子序和

输出格式

一个数，数出他们的最大子序和

测试样例1

输入

6 4 
1 -3 5 1 -2 3

输出

7

备注

数据范围：
100%满足n,m<=300000 是不超过m,不是选m个！！！！！ 
/*
单调队列优化dp
单调队列维护的是前缀和的递增序列
更新答案的时候从对首开始找第一个区间在m范围内的
f[i]表示到第i个数的不超过m的最大连续子段和,sum[i]表示i的前缀和
f[i]=max(sum[i]-sum[k])（i=> k >=i-m）,所以要找最小的sum[k]，因此用单调队列。 
*/
#include<iostream>
#include<cstdio>  using namespace std;
int n,m,tot,head,tail,x,k;  struct node{  int v,u; //v代表值，u代表下标用来判断是否超过m 
}q[100001];  int main()  
{  scanf("%d%d",&n,&m);  scanf("%d",&tot);//第一个元素  head=1;tail=2;  q[head].v=tot;q[head].u=1;  k=tot;for(int i=2;i<=n;i++)  {  scanf("%d",&x);  tot+=x;  while(q[tail-1].v>=tot && tail-1>=head) tail--;//队列中只有一个元素且比当前和大，更新 q[tail].v=tot;  q[tail].u=i;//记录下标  tail++;if(i-q[head].u>m) head++;//确定区间m if(tot-q[head].v>k) k=tot-q[head].v;  //更新答案 
    }  printf("%d\n",k);  return 0; 
}

 

转载于:https://www.cnblogs.com/L-Memory/p/6361377.html

相关文章：