一、求出这个最大连续非空数组的和

#include<iostream>
using namespace std;
int a[200000],dp[200000];
int main(){
    int n,i;
    cin>>n;
    //从0开始
    for(i = 0;i < n;i++){
        cin>>a[i];
    } 
    //初始化一下
    dp[0] = a[0];
    int res = dp[0];
    //从1开始防止数组溢出
    for(i = 1;i < n; i++){
        dp[i] = std::max(dp[i-1] + a[i] , a[i]);
        res = std::max(res , dp[i]);
    }
    cout<<res;
    return 0;
}
// 64 位输出请用 printf("%lld")

算法的基本思想：

这段代码实现了求解最大子数组和的问题，使用了动态规划的思想。

在每个位置i处，维护一个dp数组，表示以i结尾的最大子数组和。

对于每个位置i，dp[i]的值可以通过dp[i-1]和a[i]的值来计算，即dp[i] = max(dp[i-1]+a[i],a[i])。

同时，用一个变量res来记录最大的dp[i]值，即为最终的最大子数组和。

时间复杂度为O(n)，其中n是数组的大小。

空间复杂度也为O(n)，因为动态规划数组`dp`的大小与输入数组相同。

二、要保存这个非空连续最大数组返回

#include <algorithm>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型vector
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& a) {
        // write code here
        vector<int> res;
        vector<int> dp(a.size(), 0);
        
        dp[0] = a[0];
        int max_val = a[0];//注意初始化
        
        int left = 0,right = 0;
        int res_l = 0,res_r = 0;

        for (int i = 1; i < a.size(); i++) {
            right++;
            dp[i] = std::max(dp[i-1] + a[i], a[i]);
            if (dp[i-1] + a[i] < a[i]) {
                left = right;
            }
            if (dp[i] > max_val || dp[i] == max_val
            && (right - left + 1) > (res_r - res_l + 1)) {
                max_val = dp[i];
                res_l = left;
                res_r = right;
            }
        }

        for (int i = res_l; i <= res_r; i++) {
            res.push_back(a[i]);
        }
        return res;
    }
};
static const auto io_sync_off = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}
();//加速的罢了

算法基本思想：

使用动态规划的思想，维护一个数组dp，dp[i]表示以第i个元素结尾的子数组的最大和。对于每个元素，如果前面的子数组和为负数，则直接从当前元素开始重新计算，否则加上前面的子数组和。同时记录最大值和最大子数组的左右端点。

时间复杂度：

O(n)，需要遍历整个数组。

空间复杂度：

O(n)，需要维护一个长度为n的dp数组。