lc 53 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.
方法一
首先想到的就是比较暴力，没有技巧性可言的时间复杂度为O(\(n^{2}\))的方法。显而易见，这个方法重复计算了很多，非常没有效率。
int maxSubArray(int* nums, int numsSize) {
int max = nums[0];
for (int i = 0; i < numsSize; i++) {
int sum = nums[i];
if (sum >= max) max = sum;
for (int j = i+1; j < numsSize; j++) {
if (max <= sum+nums[j])
max = sum+nums[j];
sum += nums[j];
}
}
return max;
}
方法二
这道题目还可以利用动态规划的算法，通过维护全局最优变量和局部最优变量，局部最优是一定要包含当前元素，local = (local < 0) ? nums[i] : local+nums[i];。有了当前一步的局部最优，那么全局最优就是当前的局部最优或者还是原来的全局最优，global = (local > global) ? local : global;。
这个动态规划方法的时间复杂度可以降低到O(n),可以说是非常acceptable了。
int maxSubArray(int* nums, int numsSize) {
int global = nums[0], local = nums[0];
for(int i = 1; i < numsSize; i++) {
local = (local < 0) ? nums[i] : local+nums[i];
global = (local > global) ? local : global;
}
return global;
}