【问题描述】
八戒押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