最大子段和

港控/mmm° 2022-01-10 10:53 253阅读 0赞

送分题(songfen)  
Time Limit:1000ms Memory Limit:128MB

题目描述  
LYK喜欢干一些有挑战的事，比如说求区间最大子段和。它知道这个题目有O(n)的做法。于是它想加强一下。  
也就是说，LYK一开始有n个数，第i个数字是ai,它找来了一个新的数字P，并想将这n个数字中恰好一个数字替换成P。要求替换后的最大子段和尽可能大。  
LYK知道这个题目仍然很简单，于是就扔给大家来送分啦~  
注：最大子段和是指在n个数中选择一段区间\[L,R\]（L<=R）使得这段区间对应的数字之和最大。

输入格式(songfen.in)  
第一行两个数n,P。  
接下来一行n个数ai。

输出格式(songfen.out)  
一个数表示答案。

输入样例  
5 3  
\-1 1 -10 1 -1

输出样例  
5

样例解释  
将第三个数变成3后最大子段和为\[2,4\]。

数据范围  
对于30%的数据n<=100。  
对于另外30%的数据ai,P>=0。  
对于100%的数据n<=1000，-1000<=ai,P<=1000。

O(n)来求最大子段和

#include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<cstdio>
    using namespace std;
    int n,P,a[1009],ans;
    int main()
    {
        scanf("%d%d",&n,&P);
        for(int i=1;i<=n;i++)
         scanf("%d",&a[i]);
        for(int x=1;x<=n;x++)
        {
            int s=0;
            for(int i=1;i<=n;i++)
            {
                if(i==x) s+=P;//枚举的替换的第x个 
                else s+=a[i];
                if(s<0) s=0;
                ans=max(ans,s);
            }
        }
        printf("%d",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/dfsac/p/7587900.html

发表评论取消回复

表情：

评论列表（有 0 条评论，253人围观）

还没有评论，来说两句吧...

相关阅读

相关最大子段和问题

最大子段和问题描述给定由n个整数(可能为负整数)组成的序列a1，a2， a3… ， an，寻找它的某个连续子段，使得其和最大。例如( -2,11,-4,13,

妖狐艹你老母/ 2024年03月17日 09:53/ 0 赞/ 66 阅读

相关最大子段和问题

最大子段和问题。给定由n个整数组成的序列，求序列中子段的最大和，若所有整数均为负整数时定义最大子段和为0。例如, 当（a1,a2,a3,a4 ,a5,a6) = （-2,11

心已赠人/ 2023年10月05日 13:29/ 0 赞/ 41 阅读

相关 P1115-最大子段和

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

不念不忘少年蓝@/ 2023年06月01日 08:49/ 0 赞/ 18 阅读

相关 POJ 1050 最大子段和的延伸最大子矩阵

1050计算最大子矩阵，枚举行（连续的），加到一个一维数组中，再利用一个一维数组求最大子矩阵的方法，得到临时的最大子段和，枚举结束之后，得到的就是整个矩阵的最大子段和了。 j

野性酷女/ 2022年09月30日 03:46/ 0 赞/ 175 阅读

相关最大子段和

问题描述：给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。依此定义，所求的最优

雨点打透心脏的1/2处/ 2022年08月08日 06:38/ 0 赞/ 202 阅读

相关最大子段和

给定n个整数（可能包含负数）组成的序列，求该序列子段和的最大值。参考代码：常规方法1 对所有可能进行遍历，找到最终结果 include<stdio.h>

旧城等待，/ 2022年08月02日 06:44/ 0 赞/ 210 阅读

相关最大子段和动态规划实现

找到《最大子段和问题的动态规划求解》的pdf，讲解很透彻。 public class Main { public static void ma

偏执的太偏执、/ 2022年06月18日 11:08/ 0 赞/ 326 阅读

相关循环数组最大子段和

N个整数组成的循环序列a 1 1,a 2 2,a 3 3,…,a n n，求该序列如a i i\+a i\+1 i+1\+…+a j j的连续的子段和的最大值（循环序列是指n个

傷城~/ 2022年06月12日 12:07/ 0 赞/ 203 阅读

相关数据结构：最大子段和问题

最大字段和问题是这样的，在一个给定的数组中寻找子数组之和的最大值，暴力肯定是超时的，这个是个典型的动态规划DP 不过下面的做法还有点不恰当，当所有的元素都是负数的时候

今天药忘吃喽~/ 2022年05月31日 12:51/ 0 赞/ 198 阅读

相关最大子段和

送分题(songfen) Time Limit:1000ms Memory Limit:128MB 题目描述 LYK喜欢干一些有挑战的事，比如说求区间最大子段和。它知

港控/mmm°/ 2022年01月10日 10:53/ 0 赞/ 254 阅读