Subarray Sum

• brute force
• 用Hashtable记录每个index时的sum值，如果遇到重复出现的值，则代表这之间的数字之和必为0

Maximum Average SubArray

1. 累积和数组，即用一个数组sum[]来保存从0-ith的数的sum。则要求的转化为求Max(sum[i]-sum[i-k])

   for (int i = 0; i < nums.length; i++)
    nums[i]+= nums[i-1];
   

2. 滑动窗口，每次加入第i个，减去第i-k个

Maximum Average SubArray-ii

Maximum Size SubArray Sum Equals to K

• Subarray sum 问题记得初始化处理都是获得从Oth - ith数的sum。则只要有某个sum[i]-sum[j] == k，则说明存在这样的数组。所以可以查找hash表中是否有这样的sum[j]满足sum[i]-k
• 用HashMap保存这个前i个和，以及i的位置。这里用了two sum的思想
• 注意初始化map.put(0, 1) 代表的是0th之前的值。
• 另外map.containsKey的时候不更新，因为要求的是max，若是min则要更新
• 理解put的时候，只需要put最接近0的index，因为题目要求最大的size，所以只有第一次出现这个sum的时候是有用的

public int maxSubArrayLen(int[] nums, int k) {
    int sum = 0, max = 0;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; i++) {
        sum = sum + nums[i];
        if (sum == k) max = i + 1;
        else if (map.containsKey(sum - k)) max = Math.max(max, i - map.get(sum - k));
        if (!map.containsKey(sum)) map.put(sum, i);
    }
    return max;
}public int maxSubArrayLen(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        int len = nums.length;
        int[] sums = new int[len];        
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int ans = 0;
        sums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sums[i] = sums[i-1] + nums[i];
        }

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(sums[i] - k)) {
                ans = Math.max(ans, i - map.get(sums[i] - k));
            }

            if (!map.containsKey(sums[i])) {
                map.put(sums[i], i);
            }
        }        
        return ans;
    }

Subarray Sum equals K

• 与上一题很类似
• 必须在一个循环里完成，因为sum(0, j) - k = sum(0, i)的条件是j - 1 >= i 所以在判断是否存在与HashMap的时候，只能判断之前的点。而如果先构建完HashMap以后，frequency就有可能包含了之后的点，这样就无法构成合理的解

    public int subarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        HashMap < Integer, Integer > map = new HashMap < > ();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k))
                count += map.get(sum - k);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

Maximum Product Subarray

• 充分利用了contiguous subarray的特性，只需要一次循环。
• 因为是求乘积，需要保留max和min，所以在每一次的循环中max和min就由当前的max(min)与当前的数的乘积，或者当前的数本身来决定
  • 这样的话，永远保证这个max，min是跟当前这个点直接相连的
  • 当出现0的情况的时候，就可能存在要取当前的数

Best time to buy and sell stock

可以画出曲线图来，发现只需要维护minValue和maxProfix两个值即可

public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice)
                minprice = prices[i];
            else if (prices[i] - minprice > maxprofit)
                maxprofit = prices[i] - minprice;
        }
        return maxprofit;
    }

Follow up II

可以交易多次的情况下，需要画图看波峰和波谷，最好的结果是只要在波谷之后就进行操作卖出。由图可以发现，对于连续上升的子数列，卖多次和最后卖一次的结果是一样的。

class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;
    }
}