首页 > itarticle > PU Maximum Subarray

PU Maximum Subarray

admin 11月 12, 2020 0

Jan 01, 1970

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example:

given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

C Solution 1:

int maxSubArray(int* nums, int numsSize) {
    int res = nums[0], min = 0, sum = nums[0];
    int i;
    for (i = 1; i < numsSize; i++) {
        min = min < sum ? min : sum;
        sum += nums[i];
        res = res > sum - min ? res : sum - min;
    }
    return res;
}

C Solution 2:

int maxSubArray(int* nums, int numsSize) {
    int res = nums[0], pre = nums[0];
    int i;
    for (i = 1; i < numsSize; i++) {
        pre = pre < 0 ? nums[i] : pre + nums[i];
        res = res > pre ? res : pre;
    }
    return res;
}

Summary:

Solution 1: sum, prefix sum.
Solution 2: dp

LeetCode: 53. Maximum Subarray