题目描述

  给定一个长度为 $N$ 的数组 $A$，其任意连续子序列可以表示为 $A_i, A_{i+1}, ..., A_j$，其中 $0\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]$ 的答案为 $20$。

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

提交

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

#include "Solution.h"

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

    
    return 0;
}

限制

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

样例

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

6
-2 11 -4 13 -5 -2

20