首页 > 其他分享 >最大子段和动态规划

最大子段和动态规划

时间:2022-08-16 23:24:41浏览次数:62  
标签:10 maxa 子段 int 样例 100001 动态 规划

【问题描述】

  八戒押x两银子,猫掌柜给定一个乱序数组arr,长度为N,有正数也有负数,正数表示赢钱,负数表示输钱。求arr的一个连续子数组,使得子数组的和最大,这样八戒才能尽可能的赢钱。这个和最大的子数组叫做最大子段和。

输入:第一行有两个数字,分别是x和N,用空格隔开,1<=x,N<=100000,第行有N个数字,用空格隔开,表示数组元素。

输出:输出八戒最多赢多少钱,若八戒想即时止损,则输出一个负数,表示八戒最少输多少钱。

【样例输入1】

  12 8

  1 -2 3 10 -4 7 2 -5

【样例输入2】 

  6

【样例输出1】

  9 9

  -2 1 -3 4 -1 2 1 -5 4

【样例输出2】 

  -3

#include<iostream>
using namespace std;
int a[100001];
// 暴力求解循环嵌套。 
int main(){
    int x, n, sum;
    cin>>x>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    int maxa=a[1]; //假设最大值为第一个数字。
    // 1 -2 3 10 -4 7 2 -5
    for(int i=1; i<=n; i++){ // 循环n次。
        sum=0; // 开始累加。 
        for(int j=i; j<=n; j++){
            sum+=a[j];
            maxa=max(maxa, sum);
        }
    } 
    cout<<maxa-x;
    return 0;
}
#include<iostream>
using namespace std;
int a[100001], dp[100001]; 
int main(){
    int x, n, maxa;
    cin>>x>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
     maxa =a[0];  //假设最大值为第一个数字。
     dp[0]=a[1];
    // 1 -2 3 10 -4 7 2 -5
    // 1 -1 3 13 9 16 18 13
    for(int i=2; i<=n; i++){ 
        // 上一个元素小于0,则舍去,从当前元素开始算起。 
        if(dp[i-1]<0) dp[i]=a[i]; 
        else dp[i]=a[i]+dp[i-1]; 
        maxa=max(maxa, dp[i]);
    } 
    cout<<maxa-x;
    return 0;
}

 

标签:10,maxa,子段,int,样例,100001,动态,规划
From: https://www.cnblogs.com/dks0313/p/16593357.html

相关文章

  • vue学习之------动态组件
    vue提供了一个组件的占位符 ————<component:is="组件名"></component>,用来实现动态切换组件的显示与隐藏父组件中:  如果希望切换组件时,不要销毁组件,可以......
  • 最长递增子序列-动态规划
    【问题描述】有一个长度为N的乱序数组,请找到一个子序列,使得这个子序列元素的值依次递增,并且这个子序列的长度最长。注意,数组一旦给定,每个元素的位置就确定了,不可以交......
  • 自定义listview向其中动态增加控件
    1privatevoidInitARListView()2{3intcount=arListView1.Items.Count;4arListView1.Items.Clear();5......
  • EasyExecl导出模板,实现动态下拉列
    1.需要效果.  2.引入的jar包.<dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><......
  • 动态开点线段树
    动态开点线段树为了准备google的面试刷题的时候发现这个知识点其实我一直不太熟悉,所以专门写一篇blog准备一下。我们将从以下几个方面去讲解:目录动态开点线段树什么是......
  • Element cascader动态加载
    一开始也是网上查找:https://blog.csdn.net/lgh1206/article/details/113932595 看的这位博主的,他是自己创建的数据我这边是与后端联调: <el-cascader......
  • 在线动态图连通性
    动态图连通性再这样下去要被自己蠢死维护一副图,支持\(\operatorname{link,cut}\),判断\(x,y\)是否在同一个联通块中最\(naive\)的就是每次双端\(\operatorname{b......
  • C++动态链接库(DLL)文件的创建和调用
    出处:蓟_可爱的叔https://www.cnblogs.com/wjq13752525588/p/16364956.html 一、什么是库    我们在编写C/C++等语言程序的时候,经常会遇到很多反复使用的或者......
  • mybatis 10: 动态sql --- part2
    <foreach>标签作用用来进行循环遍历,完成循环条件的查询,批量删除,批量增加,批量更新用法包括循环查询+批量删除+批量增加+批量更新的用法UsersMapper.javap......
  • 注解和反射之动态创建对象执行方法
    点击查看代码packagecom.kuang.reflection;importjava.lang.reflect.Constructor;importjava.lang.reflect.Field;importjava.lang.reflect.InvocationTarget......