洛谷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;
}



相关文章
|
6月前
不要62(数位dp)
不要62(数位dp)
42 0
|
6月前
数位dp(计数问题)
数位dp(计数问题)
|
6月前
C. Unlucky Numbers(数位dp)
C. Unlucky Numbers(数位dp)
|
6月前
[leetcode ~dp ]279. 完全平方数
[leetcode ~dp ]279. 完全平方数
|
算法 Java 测试技术
dp算法 力扣152乘积最大子数组
dp算法 力扣152乘积最大子数组
|
Java
「日更刷题」59.螺旋矩阵
「日更刷题」59.螺旋矩阵
74 0
|
人工智能 算法 程序员
还不会做最大子段和?
最大子段和一定是每个(准)程序员都接触过的问题,题目很简洁:给出一个长度为 n 的序列a,选出其中连续且非空的一段使得这段和最大。为什么每个(准)程序员都需要掌握呢?首先这问题解法很多,时间复杂度从O(n3) -> O(n2) -> O(nlog2n) -> O(n)。通过解决这个问题可以体会到不同算法的效率差异,其次几种解法中包含分治、前缀和、贪心……等很多算法思想,深入理解最大子段和问题可以举一反三,映射到许多其他问题。