053 - Maximum Subarray

本文主要是介绍053 - Maximum Subarray，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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.

click to show more practice.

int domerge(int *nums, int *nsize)
{int kk = 0, k = *nsize, i;if (nums[0] < 0) kk++;for (i = kk+1; i <= k; i++) {if (nums[i] < 0) {if (i == k) break;if (nums[i] + nums[kk] >= 0 && nums[i] + nums[i + 1] >= 0) {nums[kk] += nums[i] + nums[i + 1];i++;	} else {nums[++kk] = nums[i];}} else {if (nums[kk] >= 0)nums[kk] += nums[i];else nums[++kk] = nums[i];}}if (kk == *nsize) return 0;*nsize = kk;return 1;
}int listmax(int *nums, int numsSize)
{if (numsSize < 1) return 0;if (numsSize == 1) return nums[0];if (nums[0] <= 0) return nums[0] + listmax(nums + 1, numsSize - 1);int nextgt0 = listmax(nums + 2, numsSize - 2);if (nums[1] + nextgt0 >= 0)return nums[0] + nums[1] + nextgt0;elsereturn nums[0];
}
int maxSubArray(int *nums, int numsSize)
{int max = INT_MIN;int i, k = 0;if (!numsSize) return 0;/* merge +/- */for( i = 0 ; i < numsSize ; i++ ) {if (nums[i] > max) max = nums[i];if (!i || !nums[i]) continue;if (nums[i] >= 0) {if (nums[k] >= 0) nums[k] += nums[i];else nums[++k] = nums[i];} else {if (nums[k] > 0) nums[++k] = nums[i];else nums[k] += nums[i];}}if (k == 0) return nums[k] <= 0? max:nums[k];/* merge +a -b +c --> a+b>=0 && b+c>=0 */while (domerge(nums, &k));max = INT_MIN;int left = 0, right = k, sum;while (left <= right) {if (nums[left] <= 0) {left++;continue;}sum = listmax(nums + left, k+1-left);if (sum > max) max = sum;left++;}return max;
}

这篇关于053 - Maximum Subarray的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---