Maximum Subarray
Example
Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.
public class Solution {
/*
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(int[] nums) {
// write your code here
if (nums == null || nums.length == 0) {
return Integer.MIN_VALUE;
}
int curSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
curSum = curSum > 0 ? curSum + nums[i] : nums[i];
maxSum = curSum > maxSum ? curSum : maxSum;
}
return maxSum;
}
}
Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example
For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
public int maxProduct(int[] nums) {
// write your code here
if (nums == null || nums.length == 0) {
return 0;
}
int minPre = nums[0], maxPre = nums[0];
int max = nums[0], min = nums[0];
int res = nums[0];
for (int i = 1; i < nums.length; i ++) {
max = Math.max(nums[i], Math.max(maxPre * nums[i], minPre * nums[i]));
min = Math.min(nums[i], Math.min(maxPre * nums[i], minPre * nums[i]));
res = Math.max(res, max);
maxPre = max;
minPre = min;
}
return res;
}
