dp学习——最大字段和

喜欢ヅ旅行 2022-08-21 00:18 182阅读 0赞

输入

第1行：整数序列的长度N（2 <= N <= 50000)  
第2 - N + 1行：N个整数（-10^9 <= A\[i\] <= 10^9）

输出

输出最大子段和。

输入示例

6  
\-2  
11  
\-4  
13  
\-5  
\-2

输出示例

20

> 这道题也可以用二重循环、三重循环做，但用dp可以更有效的得到解，dp数组的含义：定义dp\[i\]为输入的以a\[i\]结尾的最大字段和。  
> 状态转移方程为  
> dp\[0\] = a\[0\],  
> dp\[i\] = Max(a\[i\],a\[i\]+dp\[i-1\])  
> note:如果dp\[i-1\]是负数，那么dp\[i\]直接取a\[i\],否则就令dp\[i\]=dp\[i-1\]+a\[i\]

要注意的一个细节是如果题目的输入数据可能很大，累加求和后可能会超出int的范围，所以用了long。

import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                int n = in.nextInt();
                long[] nums = new long[n+10] , dp = new long[n+10];
                for(int i=0;i<n;i++) nums[i] = in.nextInt();
                long ans = dp[0] = nums[0];
                for(int i=1;i<n;i++){
                    dp[i] = Math.max(nums[i], dp[i-1]+nums[i]);
                    if(ans<dp[i]) ans = dp[i];
                }
                System.out.println(ans);
            }
        }
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关 51nod1050 循环数组最大子段和 dp

N个整数组成的循环序列a\[1\],a\[2\],a\[3\],…,a\[n\]，求该序列如a\[i\]+a\[i+1\]+…+a\[j\]的连续的子段和的最大值（循环序列是指

谁借莪１个温暖的怀抱￠/ 2024年02月17日 19:20/ 0 赞/ 81 阅读

相关最大字段和

最大字段和 C - 顺序表应用7：最大子段和之分治递归法 Description 给定n(1<=n<=50000)个整数（可能为负数）组成的序列a\[1\],a\

╰+攻爆jí腚メ/ 2023年01月13日 09:28/ 0 赞/ 154 阅读

相关 dp之最大和，m段最大和以及最大子矩阵

前一段时间因为要讲课学习了dp系列算法，学习了很多东西，给大一菜鸟讲了这个系列的算法，当时没有记录，前几天拿起来发现有点忘记了，所以在这里记录一下，最大和系列算法。首先子串

系统管理员/ 2022年09月20日 09:26/ 0 赞/ 167 阅读

相关 dp学习——最大字段和

输入第1行：整数序列的长度N（2 <= N <= 50000) 第2 - N + 1行：N个整数（-10^9 <= A\[i\] <= 10^9）输出输出最大子

喜欢ヅ旅行/ 2022年08月21日 00:18/ 0 赞/ 183 阅读

相关最大子段和

问题描述：给定由n个整数（包含负整数）组成的序列a1,a2,...,an，求该序列子段和的最大值。当所有整数均为负值时定义其最大子段和为0。依此定义，所求的最优

雨点打透心脏的1/2处/ 2022年08月08日 06:38/ 0 赞/ 214 阅读

相关最大子段和

给定n个整数（可能包含负数）组成的序列，求该序列子段和的最大值。参考代码：常规方法1 对所有可能进行遍历，找到最终结果 include<stdio.h>

旧城等待，/ 2022年08月02日 06:44/ 0 赞/ 226 阅读

相关最大字段和

N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。

- 日理万妓/ 2022年07月29日 11:50/ 0 赞/ 200 阅读

相关分治法解决最大字段和问题

分治法求解最大字段和问题 1 问题描述　　给定由n个整数（可能由负数）组成的序列（a1, a2,...,an),最大字段和问题求该序列中连续子段和的最大值，并找出这

我不是女神ヾ/ 2022年04月12日 09:39/ 0 赞/ 306 阅读

相关动态规划--求数列的最大字段和

【问题描述】 N个整数，需要从中找出连续的一段数串，使得这串数的和最大。例如-2,11，-4,13，-5，-2, 最大的子串为11，-4,13。则最大字段和为11-4

我就是我/ 2022年03月30日 13:18/ 0 赞/ 272 阅读

相关最大子段和

送分题(songfen) Time Limit:1000ms Memory Limit:128MB 题目描述 LYK喜欢干一些有挑战的事，比如说求区间最大子段和。它知

港控/mmm°/ 2022年01月10日 10:53/ 0 赞/ 263 阅读