最大序列和

[编程题]最大序列和

热度指数：28417 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。对于S的所有非空连续子序列T，求最大的序列和。变量条件：N为正整数，N≤1000000，结果序列和在范围（-2^63,2^63-1）以内。

输入描述:

第一行为一个正整数N，第二行为N个整数，表示序列中的数。

输出描述:

输入可能包括多组数据，对于每一组输入数据，
仅输出一个数，表示最大序列和。

示例1

输入

5
1 5 -3 2 4

6
1 -2 3 4 -10 6

4
-3 -1 -2 -5

输出

9
7
-1

算法知识视频讲解

健康快乐最重要

发表于 2020-02-25 17:37:38

a[i]表示以第i个元素为结尾的最大子序列和。通过一个例子我们可以推导出此递归产生式：a[i]=max(a[i],a[i-1]+a[i]); 比如1 5 -3 2 4a[0]=1;a[2]=1+5=6;a[3]=1+5+(-3)=3;a[4]=3+2=5;a[6]=5+4=9; 1 -2 3 4 - 展开全文

philos

发表于 2021-02-05 10:50:18

思路求最大子序列和，我们可以使用动态规划的思路，dp[i] 表示以 nums[i] 结尾的最大和，那么 dp[i] = max(dp[i-1] + nums[i], nums[i]) = dp[i-1] > 0 ? dp[i-1] + nums[i] : nums[i] #include&l 展开全文

用户抉择

发表于 2021-03-03 10:48:32

有点类似递增数列求和 #include <stdio.h> int main() { int n,i,max; while(scanf("%d",& 展开全文

牛客440904392号

发表于 2024-08-11 18:54:43

#include <bits/stdc++.h> //#include <iostream> //#include <vector> //#include <climits> //#include <algorithm> using nam 展开全文

牛客588682307号

发表于 2024-03-13 18:02:14

# include<stdio.h> int main(){ int n; while(scanf("%d",&n)!=EOF){ int nums[n]; for(int i=0;i<n;i++) scanf("% 展开全文

不由天的命

发表于 2024-09-14 19:53:10

Kadane算法是一种非常适合用来求最大序列和的算法，其核心思想就是判断当前的序列和与当前元素之间的大小关系：如果是序列和大，则存储当前序列和；若当前元素大，则认为取当前元素即为最大，将当前序列和设为当前元素的值；如此遍历完所有元素即可获得最大元素和，Kadane算法的时间复杂度为 O(n)。C语言展开全文

在考古的小鱼干很有气魄

发表于 2023-03-09 10:51:42

#include <bits/stdc++.h> #define MAX 1000000 using namespace std; int main() { int n, dp[MAX]; while (cin >> n) { for (in 展开全文

Perceive109

发表于 2023-03-25 12:19:56

#include "iostream" #include "vector" using namespace std; // 思路： // 从最后一个节点出发，不断计算局部最大值并将其保存至dp // 具体思路：对比自身 & 自身+dp[i+1] 取最大值 // 举例分析： // 如 1 5 -3 展开全文