首页 > itarticle > maximum subarray

maximum subarray

admin 1月 11, 2021 0

问题来源
问题简介

给出一个数组（个数大于1），要求你算出该数组的所有连续子数组中所有数的和的最大值。

解题思路

时间复杂度	空间复杂度
O(未知)	O(未知)

Code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size(), maximum = 0, *dp = new int[len];
        dp[0] = nums[0];
        maximum = dp[0];
        for (int i = 1; i < len; i++) {
            dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            maximum = max(maximum, dp[i]);
        }
        delete [] dp;
        return maximum;
    }
};

运行结果