Lintcode: Maximum Subarray Difference

用到了max subarray的技巧，并且分别从左边和右边扫，对于每一个index， 更新res = Math.max(res, Math.max(maxFromRight[i] – minFromLeft[i-1], maxFromLeft[i] – maxFromRight[i-1]));

public class Solution {
    public int maxDiffSubArrays(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) {
            return 0;
        }
        int[] maxFromLeft = new int[nums.size()];
        int[] minFromLeft = new int[nums.size()];
        int min = nums.get(0);
        int max = min;
        int localmin = min;
        int localmax = max;
        maxFromLeft[0] = minFromLeft[0] = min;
        for (int i = 1; i < nums.size(); i++) {
            localmin = Math.min(nums.get(i), localmin+nums.get(i));
            localmax = Math.max(nums.get(i), localmax+nums.get(i));
            max = Math.max(max, localmax);
            min = Math.min(min, localmin);
            maxFromLeft[i] = max;
            minFromLeft[i] = min;
        }
        min = nums.get(nums.size() - 1);
        max = min;
        localmin = min;
        localmax = max;
        int res = Math.max(max - minFromLeft[nums.size()-2],
                           maxFromLeft[nums.size() - 2] - min);
        for (int i = nums.size() - 2; i > 0; i--) {
            localmin = Math.min(nums.get(i), localmin+nums.get(i));
            localmax = Math.max(nums.get(i), localmax+nums.get(i));
            max = Math.max(max, localmax);
            min = Math.min(min, localmin);
            res = Math.max(res, Math.max(max - minFromLeft[i-1],
                           maxFromLeft[i-1] - min));
        }
        return res;
    }
}

Lintcode: Maximum Subarray II

public class Solution {
    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) {
        	return 0;
        }
        int[] fromLeft = new int[nums.size()];
        int[] fromRight = new int[nums.size()];
        int global = Integer.MIN_VALUE;
        int local = 0;
        for (int i = 0; i < nums.size(); i++) {
        	local = Math.max(nums.get(i), nums.get(i) + local);
        	global = Math.max(global, local);
        	fromLeft[i] = global;
        }
        local = 0;
        global = Integer.MIN_VALUE;
        for (int j = nums.size() - 1; j >= 0; j--) {
        	local = Math.max(nums.get(j), nums.get(j) + local);
        	global = Math.max(global, local);
        	fromRight[j] = global;
        }
        local = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size() - 1; i++) {
        	local = Math.max(local, fromLeft[i] + fromRight[i+1]);
        }
        return local;
    }
}

Lintcode: product of subarray exclude itself

左右分别scan法。

public class Solution {
    public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
        ArrayList<Long> res = new ArrayList<Long>();
        if (A == null || A.size() == 0) {
          return res;
        }
        if (A.size() == 1) {
            res.add(1L);
            return res;
        }
        Long[] left = new Long[A.size()];
        Long[] right = new Long[A.size()];
        long product = 1;
        for (int i = 0; i < A.size(); i++) {
          product*= A.get(i);
          left[i] = product;
        }
        product = 1;
        for (int i = A.size()-1; i >= 0; i--) {
          product *= A.get(i);
          right[i] = product;
        }
        for (int i = 0; i < A.size(); i++) {
          if (i == 0) {
            res.add(right[i+1]);
          } else if (i == A.size() - 1) {
            res.add(left[i-1]);
          } else {
            res.add(left[i-1] * right[i+1]);
          }
        }
        return res;
    }
}