A. 最大子序列(DP)

    Type: Default 1000~1500ms 256MiB

最大子序列(DP)

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

  给定一个长度为 NN 的数组 AA,其任意连续子序列可以表示为 Ai,Ai+1,...,AjA_i, A_{i+1}, ..., A_j,其中 0ijN10\leq i \leq j \leq N-1

  最大子序列是指所有子序列中和最大的那一个,注意子序列 不能为空。为了降低难度,你需要输出它的和,即

$$result = \max_{0 \leq i \leq j \leq N-1}\sum_{k=i}^j A[k] $$

  例如,[2,11,4,13,5,2][-2, 11, -4, 13, -5, -2] 的答案为 2020

  请使用 动态规划 思想完成 Solution.hpp 的实现

提交

  请在下述代码基础上进行实现,完成函数后提交

#include "Solution.h"

long long Solution::find_maximum_subarray(vector<int> &A) {
    // 请在这里完成你的代码

    
    return 0;
}

限制

1N106,A[i]1091 \leq N \leq 10^6, \left| A[i] \right| \leq 10^9

样例

  你的程序 不需要输入输出,提供一组样例用于自测。

6
-2 11 -4 13 -5 -2
20

实验四 动态规划

Not Claimed
Status
Done
Problem
6
Open Since
2024-10-19 14:00
Deadline
2024-10-19 18:00
Extension
144 hour(s)