Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

难度：medium

Solution: Dynamic Programming

public class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
        dp[0] = nums[0];
        int maxSum = dp[0];

        for(int i = 1; i < n; ++i){
            dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            maxSum = Math.max(maxSum, dp[i]);
        }

        return maxSum;
    }
}

更加精简的版本

public class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE, curSum = 0;
        for(int i = 0; i < nums.length; ++i) {
            curSum += nums[i];
            if(maxSum < curSum) {
                maxSum = curSum;
            }
            if(curSum < 0) {
                curSum = 0;
            }
        }

        return maxSum;
    }
}

Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

难度：medium

Solution: Dynamic Programming

class Solution {
    public int maxProduct(int[] nums) {
        int pro = nums[0];
        int maxPro = 1;
        int minPro = 1;
        int m = nums.length;
        for(int i = 0; i < m; ++i) {
            if(nums[i] > 0) {
                maxPro = Math.max(maxPro * nums[i], nums[i]);
                minPro = Math.min(minPro * nums[i], nums[i]);
            } else {
                int temp = maxPro;
                maxPro = Math.max(minPro * nums[i], nums[i]);
                minPro = Math.min(temp * nums[i], nums[i]);
            }
            pro = Math.max(maxPro, pro);
        }

        return pro;
    }
}

Minimum Size Subarray Sum

Medium

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Solution: Two Pointers

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i = 0, j = 0;
        long sum = 0;
        long length = nums.length + 1;
        while(j < nums.length) {
            sum += nums[j];
            while(sum >= s) {
                length = Math.min(length, j - i + 1);
                sum -= nums[i];
                ++i;
            }
            ++j;
        }
        return (int)(length == nums.length + 1 ? 0 : length);
    }
}