算法分析与设计►未分类

Maximum Subarray

  • 问题来源
  • 问题简介

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

解题思路


在遍历数组时，对于当前遍历数字 num，若我们能知道直到该数字之前的连续数组的和的值 prev，就可以得到加上该数字之后的连续数组的和的值 sum。这里由于我们想得到一个最大值，故而若prev小于零，加上它只会使sum缩小，那么这时我们应该舍弃prev以num为连续数组的起点才能使直到num的连续数组的和最大。
时间复杂度 空间复杂度
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;
    }
};

运行结果

Maximum Subarray