LeetCode------Maximum SubArray
程序员文章站
2022-07-15 19:48:50
...
解法1
分治法
Divide and Conquer Approach来解,这个分治法的思想就类似于二分搜索法,我们需要把数组一分为二,分别找出左边和右边的最大子数组之和,然后还要从中间开始向左右分别扫描,求出的最大值分别和左右两边得出的最大值相比较取最大的那一个,代码如下:
/*
* 分治法的思想就类似于二分搜索法,我们需要把数组一分为二,
* 分别找出左边和右边的最大子数组之和,然后还要从中间开始向左右分别扫描,
* 求出的最大值分别和左右两边得出的最大值相比较取最大的那一个
*
* 考虑三部分:
* leftMax:左边最大子数组和
* rightMax:右边最大子数组
* midMax:从中间分别从两边扫描left~mid-1 mid+1~right
*/
public int maxSubArray(int[] nums) {
if (nums.length == 0) return 0;
return helper(nums, 0, nums.length - 1);
}
public int helper(int[] nums, int left, int right) {
if (left >= right) return nums[left];
int mid = left + (right - left) / 2;
//分别找出左右两部分最大和
int leftMax = helper(nums, left, mid - 1);
int rightMax = helper(nums, mid + 1, right);
//从中间往两边扫描,tmp保存临时的midMax
int midMax = nums[mid];
int tmp = midMax;
for (int i = mid - 1; i >= left; --i) {
tmp += nums[i];
midMax = Math.max(midMax, tmp);
}
tmp = midMax;
for (int i = mid + 1; i <= right; ++i) {
tmp += nums[i];
midMax = Math.max(midMax, tmp);
}
//返回三部分的最大值
return Math.max(midMax, Math.max(leftMax, rightMax));
}
解法2
O(n)的解法,定义两个变量res
和curSum
,其中res保存最终要返回的结果,即最大的子数组之和,curSum初始值为0,每遍历一个数字num,比较curSum + num
和num
中的较大值存入curSum,然后再把res和curSum中的较大值存入res,以此类推直到遍历完整个数组,可得到最大子数组的值存在res中,代码如下:
/*
* O(n)的解法,定义两个变量res和curSum:
* res保存最终要返回的结果,即最大的子数组之和;
* curSum初始值为0,每遍历一个数字num,比较curSum + num和num中的较大值存入curSum,然后再把res和curSum中的较大值存入res,
* 以此类推直到遍历完整个数组,可得到最大子数组的值存在res中
*/
public int maxSubArray2(int[] nums) {
int res = Integer.MIN_VALUE;
int curSum = 0;
for(int num : nums) {
curSum = Math.max(curSum+num, num);
res = Math.max(res,curSum);
}
return res;
}
解法3
动态规划
//动态规划:其实跟上面O(n)解法思想是一样的
public int maxSubArray3(int[] nums) {
int maxLocal = nums[0];
int global = nums[0];
for(int i =1;i<nums.length;i++) {
maxLocal = Math.max(nums[i],nums[i]+maxLocal);
global = Math.max(global, maxLocal);
}
return global;
}
推荐阅读
-
LeetCode------Maximum SubArray
-
leetcode【53】Maximum Subarray
-
53. Maximum Subarray
-
LintCode 722: Maximum Subarray VI (Trie, 异或经典难题)
-
HK Maximum Subarray Sum
-
LintCode 139. Subarray Sum Closest
-
Minimum Size Subarray Sum
-
Minimum Size Subarray Sum
-
lintcode-44. Minimum Subarray
-
LeetCode 560 Subarray Sum Equals K (hash)