1. Maximum Subarray

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

For example, given the array[-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray[4,-1,2,1]has the largest sum =6.

public class Solution {

    public int maxSubArray(int[] nums) {

        if(nums.length == 0) return 0;

        int max = nums[0];
        int maxEndingHere = max;

        for(int i = 1; i < nums.length; i++){
            maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
            max = Math.max(max, maxEndingHere);
        }
        return max;
    }
}

2. Maximum Product Subarray

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

For example, given the array[2,3,-2,4],
the contiguous subarray[2,3]has the largest product =6.

public class Solution {
    public int maxProduct(int[] nums) {

        if(nums.length==0)  return 0;

        int min, max;
        int minPre = nums[0];
        int maxPre = nums[0];
        int res    = nums[0];

        for(int i = 1; i < nums.length; i ++){
            min = Math.min(nums[i], Math.min(minPre * nums[i], maxPre * nums[i]));
            max = Math.max(nums[i], Math.max(minPre * nums[i], maxPre * nums[i]));

            minPre = min;
            maxPre = max;

            res = Math.max(max, res);
        }

        return res;
    }
}

3. Gas Station

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {

        int total = 0, tank = 0, start = 0;

        for(int i=0; i<gas.length; i++){
            total += gas[i] - cost[i];
            tank  += gas[i] - cost[i];

            if(tank<0){
                start = i + 1;
                tank  = 0;
            }
        }

        if(total<0)
            return -1;
        return start;

    }

4. Minimum Size Subarray Sum

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

For example, given the array[2,3,1,2,4,3]ands = 7,
the subarray[4,3]has the minimal length under the problem constraint.

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {

        if(s == 0||nums.length == 0) return 0;

        int left = 0, right = 0;
        int min_len = Integer.MAX_VALUE;
        int len = nums.length;
        int sum = 0;

        while(right < len){

            sum += nums[right++];
            while(sum >= s && left < right){
                min_len = Math.min(min_len, right - left);
                //left ++;
                sum -= nums[left++];
            }
        }

        return min_len == Integer.MAX_VALUE? 0: min_len;
    }
}

5. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given[10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is[2, 3, 7, 101], therefore the length is4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

public class Solution {
    public int lengthOfLIS(int[] nums) {

        if(nums.length == 0) return 0;

        int n = nums.length;
        int[] tails = new int[n];

        int size = 0;
        for(int num: nums){

            int i = 0, j = size;
            while(i < j){
                int mid = (i + j) / 2;
                if(tails[mid] < num)
                    i = mid + 1;
                else
                    j = mid;
            }

            tails[i] = num;
            if(i == size) size ++;
        }

        return size;
    }
}