洛谷P1115-最大子段和(DP-最大子段和)

简介: 洛谷P1115-最大子段和(DP-最大子段和)

题目描述:


给出一个长度为 n 的序列 a,选出其中连续且非空的一段使得这段和最大。


输入格式:



第一行是一个整数,表示序列的长度 n。

第二行有 n 个整数,第 i 个整数表示序列的第 i 个数字 ai。



输出格式:


输出一行一个整数表示答案。


输入输出样例:



输入 #1复制

7

2 -4 3 -1 2 -4 3


输出 #1复制

4

说明/提示:


样例 1 解释

选取 [3,5] 子段 {3,−1,2},其和为 4。

数据规模与约定

  • 对于 40% 的数据,保证 n≤2×10^3。
  • 对于 100% 的数据,保证 1≤n≤2×10^5,−10^4≤ai≤10^4。


AC Code:


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max(x,y) (x>y ? x:y)
#define N 200001
int dp[N],a[N];
int n,ans=-0x3f3f3f;
int main() {
  scanf("%d",&n);
  for(int i=1;i<=n;i++) {
    scanf("%d",&a[i]);
  }
  for(int i=1;i<=n;i++) {
    dp[i]=max(a[i],dp[i-1]+a[i]);
    ans=max(ans,dp[i]);
  }
  printf("%d\n",ans);
  return 0;
}



相关文章
|
19天前
|
人工智能
AcWing 274. 移动服务(线性dp)
AcWing 274. 移动服务(线性dp)
13 0
|
19天前
acwing 275 传纸条 (线性dp)
acwing 275 传纸条 (线性dp)
12 0
|
6月前
[leetcode ~dp ]279. 完全平方数
[leetcode ~dp ]279. 完全平方数
|
人工智能
动态规划(DP)——线性DP
动态规划(DP)——线性DP
|
人工智能 算法
【动态规划】最大子段和
输入一个整型数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5,和最大的子数组为3,10,-4,7,2,因此输出为该子数组的和18。
212 0
53_最大子序和
53_最大子序和
98 0