最长子序列和问题，动态规划。

佚名 6年前 (2019-05-10) 随笔 839人围观抢沙发百度已收录

输入第1行给出正整数K (≤)；第2行给出K个整数，其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

递推公式 dp[n]=max(0,dp[n-1)+num[i];

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int dp[100005]={0};
int main(){
    int n;
    scanf("%d",&n);
    int maxn=0;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        dp[i]=max(0,dp[i-1])+x;
        maxn=maxn>dp[i]?maxn:dp[i];
    }
    printf("%d",maxn);
}