44. Minimum Subarray

Leave a comment

August 20, 2016 by oneOokay

可以跟41. Maximum subarray 比较一下: http://www.lintcode.com/en/problem/maximum-subarray/

九章上po了三个解法,http://www.jiuzhang.com/solutions/maximum-subarray/, 其中也包含global & local.

但是感觉这个的第一个解法更易理解:

http://fisherlei.blogspot.com/2012/12/leetcode-maximum-subarray.html

=======================================================================

 

基本上不能用Pair的那个class,这个就要用到global min 和 local min的。总觉得以前做过这个题,当时还很理解不了global min 和local min来着。

public int minSubArray(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return 0;
}

int len = nums.size();
int min = Integer.MAX_VALUE;
int currentSum = 0;
int[] global = new int[len];
int[] local = new int[len];

for (int i = 0; i < len; i ++) {
if ( i == 0) {
global[0] = local[0] = nums.get(0);
} else {
local[i] = Math.min(local[i – 1] + nums.get(i), nums.get(i)); //求minimum sum:因为是sum,所以两种情况:加一个负数的和,或者不加,元素自己本身构成minimum sum:要在下一步的时候决定是加下一个值使得local min最小还是单取下一个值使得local min最小。在对此时的local min和之前的global min进行对比并且update global min。最终结果为global min的最后一个值。
global[i] = Math.min(global[i – 1], local[i]);
}
}

return global[len – 1];

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: