My code:
public class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
else if (nums.length == 1)
return nums[0];
int maxSum = nums[0];
int currSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currSum = currSum >= 0 ? currSum + nums[i] : nums[i];
maxSum = Integer.max(maxSum, currSum);
}
return maxSum;
}
}
My test result:
這道題目不算很難，但我知道我一定會(huì)想復(fù)雜宏赘。所以在動(dòng)手痛苦得設(shè)置狀態(tài)機(jī)之前還是決定看下別人的思路吧哮针。否則又是亂寫，浪費(fèi)時(shí)間计福「抛鳎靠if語句做出答案沪袭。思維是垃圾的。
其實(shí)面對(duì)這種妒御，求 max of sub array 的題目解愤，我每次一看到題，都會(huì)一種誤解乎莉，需要求出這個(gè)最大值送讲，方法是奸笤，找出求得這個(gè)最大值的區(qū)域范圍。
其實(shí)完全不需要哼鬓。我們只需要求最大值监右。那么，最大值可以不斷刷新异希，當(dāng)新的更大的值出現(xiàn)的時(shí)候健盒，就將maxSum刷新。而不需要記錄這個(gè)刷新值的起點(diǎn)和尾點(diǎn)是哪里称簿。
于是只需要考慮一種情況扣癣。
當(dāng) currSum < 0 時(shí)，此時(shí)后一個(gè)值加上 currSum 予跌，總sum都會(huì)變小搏色。
所以直接將 currSum = nums[i]
如果 nums[i] <= 0 善茎， 那么券册，也許,原 currSum 是要大于 此時(shí)的currSum的。
但那又如何呢垂涯？currSum保存的只是現(xiàn)在的和烁焙。而最大和，是保存在 maxSum里面的耕赘。
所以只需要比較下原maxSum 和 現(xiàn)currSum 大小即可骄蝇。取最大值。
如果 nums[i] > 0, 那么此刻操骡，因?yàn)?currSum <= 0 ,所以
currSum + nums[i] <= nums[i] 的九火。所以可以從nums[i] 重新開始，不需要加上之前的負(fù)數(shù)册招。
如果原currSum > 0 ,那就直接加上 nums[i], 不斷與maxSum比較岔激，不斷刷新maxSum即可。
**
總結(jié)： Array是掰， DP虑鼎。 求 sub array 的最大和。記住键痛，只需要求出最大和炫彩，而不需要考慮任何有關(guān)該最大和起止點(diǎn)的問題。
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int tracker = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
tracker = Math.max(tracker + nums[i], nums[i]);
max = Math.max(max, tracker);
}
return max;
}
}
剛做完 maximum subarray product,
http://www.reibang.com/p/e1456b90c819
所以這道題做起來比較快絮短。
差不多的思路江兢，用一個(gè)tracker去追蹤之前最大的和，必須與現(xiàn)在這個(gè)index相連丁频。然后杉允，再綜合找出最大值扔嵌。
Anyway, Good luck, Richardo!
一開始也是直接拿O(n) 方法做的，后來看到有 divide and conquer做法夺颤，就看了解釋痢缎，然后自己寫了一遍。
```java
public class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
return helper(nums, 0, nums.length - 1);
}
private int helper(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int middle = left + (right - left) / 2;
int leftMax = helper(nums, left, middle);
int rightMax = helper(nums, middle + 1, right);
int leftPart = Integer.MIN_VALUE;
int temp = 0;
for (int i = middle; i >= left; i--) {
temp += nums[i];
leftPart = Math.max(leftPart, temp);
}
int rightPart = Integer.MIN_VALUE;
temp = 0;
for (int i = middle + 1; i <= right; i++) {
temp += nums[i];
rightPart = Math.max(rightPart, temp);
}
int crossMax = leftPart + rightPart;
return Math.max(crossMax, Math.max(leftMax, rightMax));
}
}
只不過覺得好沒意思世澜。独旷。。太不自然的想法了寥裂，速度也很慢嵌洼。
Anyway, Good luck, Richardo!
如果問，找出這個(gè)sub array 的途徑：
My code:
public int[] maxSubArrayPath(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
int max = nums[0];
int sum = nums[0];
int begin = 0;
int end = 0;
int currBegin = 0;
int currEnd = 0;
for (int i = 1; i < nums.length; i++) {
if (sum + nums[i] >= nums[i]) {
sum += nums[i];
currEnd = i;
}
else {
sum = nums[i];
currBegin = i;
currEnd = i;
}
if (max < sum) {
begin = currBegin;
end = currEnd;
max = sum;
}
}
return new int[]{begin, end};
}
如果問封恰，找出不大于 k 的最大sub array 和
My code:
public int maxSubArrayK(int[] nums, int k) {
int n = nums.length;
int[] sums = new int[n];
int temp = 0;
TreeSet<Integer> set = new TreeSet<Integer>();
for (int i = 0; i < nums.length; i++) {
temp += nums[i];
sums[i] = temp;
set.add(temp);
}
set.add(0);
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
Integer num = set.ceiling(nums[i] - k);
if (num != null) {
max = Math.max(max, nums[i] - num);
}
}
return max == Integer.MIN_VALUE ? -1 : max;
}
Anyway, Good luck, Richardo! -- 09/24/2016
