leetcode 53.Maximum Subarray

分治法

//lSum表示[left,right]内以left为左端点的最大子段和
//rSum表示[left,right]内以right为右端点的最大字段和
//iSum表示[left,right]的区间和
int divide_conquer(int* nums,int left,int right,int *lSum,int *rSum,int *iSum){int maxSum;//表示[left,right]内的最大字段和if(left == right){*lSum = nums[left];*rSum = nums[left];*iSum = nums[left];maxSum = nums[left];return maxSum;}int mid = (left+right)/2;int lSumL,rSumL,iSumL;int maxSumL = divide_conquer(nums,left,mid,&lSumL,&rSumL,&iSumL);int lSumR,rSumR,iSumR;int maxSumR = divide_conquer(nums,mid+1,right,&lSumR,&rSumR,&iSumR);*iSum = iSumL + iSumR;*lSum = lSumL > (iSumL + lSumR) ? lSumL:(iSumL + lSumR);*rSum = rSumR > (iSumR + rSumL) ? rSumR:(iSumR + rSumL);maxSum = maxSumL > maxSumR ? maxSumL: maxSumR;if(maxSum < rSumL+lSumR)maxSum = rSumL+lSumR;return maxSum;
}int maxSubArray(int* nums, int numsSize) {int lSum,rSum,iSum;return divide_conquer(nums,0,numsSize-1,&lSum,&rSum,&iSum);
}

动态规划

第一版

int maxSubArray(int* nums, int numsSize) {if(numsSize == 1)return nums[0];int *max_sub_sum = (int*)malloc(sizeof(int)*numsSize);max_sub_sum[0] = nums[0];int max_sum = nums[0];for(int i = 1;i < numsSize;i++){max_sub_sum[i] =  max_sub_sum[i-1] + nums[i] >= nums[i] ? max_sub_sum[i-1] + nums[i]:nums[i];if(max_sub_sum[i] > max_sum)max_sum = max_sub_sum[i];}free(max_sub_sum);return max_sum;
}

分析发现，numsSize等于1的情况不用单独考虑，后面的逻辑可以涵盖这种情况：

int maxSubArray(int* nums, int numsSize) {int *max_sub_sum = (int*)malloc(sizeof(int)*numsSize);max_sub_sum[0] = nums[0];int max_sum = nums[0];for(int i = 1;i < numsSize;i++){max_sub_sum[i] =  max_sub_sum[i-1] + nums[i] >= nums[i] ? max_sub_sum[i-1] + nums[i]:nums[i];if(max_sub_sum[i] > max_sum)max_sum = max_sub_sum[i];}free(max_sub_sum);return max_sum;
}

进一步分析，发现求max_sub_sum[i]的时候，只需要用到max_sub_sum[i-1]，而不需要用到max_sub_sum数组i-1前面的元素，所以可以用一个pre_max_sub_sum取代max_sub_sum数组的作用，节省内存开销。

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