基础九子数组和前缀和

53 Maximum Subarray 找和最大子数组（找最小的话元素取反求最大就行）

从前向后计算sum同时维持最小的前缀和
dp dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0); dp[i]是已i元素结尾的子数组最大和

lt138 Subarray Sum

题目：找一个和为零的子数组
思路：转化为找两个前缀和相同的子数组中间的数和为零；
注意：要put(0, -1)；找到的和相同index返回时要加一因为是要求中间的数不包括上一个

lt139 Subarray Sum Closest 找一个和最接近零的子数组转化为找两个前缀和最接近的子数组;注意要添加Pair[0, 0] 计算下表0-2子数组和用到presum[2]-presum[-1]

Prefix Sum + Sort (Offline Algorithm)
Find the subarray sum closet to 0 => find two prefix sum closet to each other => find min difference in sorted prefix sum array
Sort (prefixSum, index) pair
Time Complexity: O(nlogn)
另一种解法
Prefix Sum + TreeMap (Online Algorithm)
Key: prefix sum Value: index
TreeMap is implemented using Red Black Tree (Balanced BST), can be used to find the closet element Ceiling/Floor
Time Complexity: O(nlogn)

121 Best Time to Buy and Sell Stock 有一点前缀和的意思不过注意这里是要求利益的前缀和所以用前缀和反而没有直接记录之前最小并维持一个全局最大利益来的简单
lt405 Submatrix Sum

题目：求一个二维数组中某个子矩阵和为零
思路：枚举上行下行并在之前做前缀和 O(n^3)
注意：和之前那个题一样要put(0, -1)；找到的和相同index返回时要加一因为是要求中间的数不包括上一个

lt944 Maximum Submatrix

题目：求一个二维数组中最大子矩阵和
思路：枚举上行下行并在之前做前缀和 O(n^3)

304 Range Sum Query 2D - Immutable
308 Range Sum Query 2D - Mutable

53. Maximum Subarray 找和最大的子数组

class Solution {
    public int maxSubArrayPrefixSum(int[] nums) {
        if(nums==null || nums.length==0)
            return 0;
        int min = 0;
        int sum = 0;
        int result = Integer.MIN_VALUE;
        for(int i=0; i<nums.length; i++){
            sum = sum+nums[i];
            result = Math.max(result, sum-min);
            min = Math.min(min, sum);
        }
        return result;
    }
}

public int maxSubArrayDP(int[] A) {
        int n = A.length;
        int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
        dp[0] = A[0];
        int max = dp[0];
        
        for(int i = 1; i < n; i++){
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }
        
        return max;
}

lt138 Subarray Sum

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    public List<Integer> subarraySum(int[] nums) {
        // write your code here
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0;
        for(int i=0; i<nums.length; i++){
            sum = sum+nums[i];
            if(map.containsKey(sum)){
                int index = map.get(sum);
                //注意这里加一
                list.add(index+1);
                list.add(i);
                return list;
            }else{
                map.put(sum, i);
            }
        }
        return list;
    }
}

139. Subarray Sum Closest

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    class pair{
        int index;
        int sum;
        pair(int index, int sum){
            this.index = index;
            this.sum = sum;
        }
    }
    public int[] subarraySumClosest(int[] nums) {
        // write your code here
        int[] result = new int[2];
        if(nums==null)
            return result;
        if(nums.length==0)
            return new int[]{0,0};
        pair[] sums = new pair[nums.length+1];
        sums[0] = new pair(0, 0);
        int prev = 0;
        for(int i=1; i<=nums.length; i++){
            // sums[i] = new pair(i, sums[i-1].sum+nums[i-1]);
            sums[i] = new pair(i, prev + nums[i-1]);
            prev = sums[i].sum;
        }
        Arrays.sort(sums, new Comparator<pair>() {
           public int compare(pair a, pair b) {
               return a.sum - b.sum;
           } 
        });
        int ans = Integer.MAX_VALUE;
        for(int i=1; i<sums.length; i++){
            if(ans>sums[i].sum-sums[i-1].sum){
                ans = sums[i].sum-sums[i-1].sum;
                result[0] = sums[i-1].index-1;
                result[1] = sums[i].index-1;
                Arrays.sort(result);
                result[0]++;
            }
        }
        return result;
    }
}

121 Best Time to Buy and Sell Stock

class Solution {
    public int maxProfit(int[] nums) {
        if(nums==null || nums.length<=1){
            return 0;
        }
        int max = 0;
        int min = Integer.MAX_VALUE;
        for(int i=0; i<nums.length; i++){
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]-min);
        }
        return max;
    }
}

lt405 Submatrix Sum

public class Solution {
    /*
     * @param matrix: an integer matrix
     * @return: the coordinate of the left-up and right-down number
     */
    public int[][] submatrixSum(int[][] matrix) {
        // write your code here
        int[][] result = new int[2][2];
        int[][] sums = new int[matrix.length][matrix[0].length];
        for(int col=0; col<matrix[0].length; col++){
            int sum = 0;
            for(int row=0; row<matrix.length; row++){
                sum = sum+matrix[row][col];
                sums[row][col] = sum;
            }
        }
        for(int top=0; top<matrix.length; top++){
            for(int bot=top; bot<matrix.length; bot++){
                Map<Integer, Integer> map = new HashMap<>();
                map.put(0, -1);
                int sum = 0;
                for(int i=0; i<matrix[0].length; i++){
                    sum = top>0 ? sum + sums[bot][i] - sums[top-1][i] : sum + sums[bot][i];
                    if(map.containsKey(sum)){
                        result[0][0] = top;
                        result[0][1] = map.get(sum)+1;
                        result[1][0] = bot;
                        result[1][1] = i;
                        return result;
                    }else{
                        map.put(sum, i);
                    }
                }
            }
        }
        return result;
    }
}

lt944 Maximum Submatrix

public class Solution {
    /**
     * @param matrix: the given matrix
     * @return: the largest possible sum
     */
    public int maxSubmatrix(int[][] matrix) {
        // write your code here
        if(matrix==null || matrix.length==0 || matrix[0].length==0)
            return 0;
        int[][] sums = new int[matrix.length][matrix[0].length];
        for(int col=0; col<matrix[0].length; col++){
            int sum = 0;
            for(int row=0; row<matrix.length; row++){
                sum  = sum + matrix[row][col];
                sums[row][col] = sum;
            }
        }
        int result = Integer.MIN_VALUE;
        for(int top=0; top<matrix.length; top++){
            for(int bot=top; bot<matrix.length; bot++){
                int sum = 0;
                int min = 0;
                for(int i=0; i<matrix[0].length; i++){
                    sum = top>0 ? sum+sums[bot][i]-sums[top-1][i] : sum+sums[bot][i];
                    result = Math.max(result, sum-min);
                    min = Math.min(min, sum);
                }
            }
        }
        return result;
    }
}

304 Range Sum Query 2D - Immutable

class NumMatrix {
    int[][] sums;
    public NumMatrix(int[][] matrix) {
        if(matrix==null || matrix.length==0 || matrix[0]==null || matrix[0].length==0)
            return;
        sums = new int[matrix.length+1][matrix[0].length+1];
        for(int i=1; i<=matrix.length; i++){
            int sum = 0;
            for(int j=1; j<=matrix[0].length; j++){
                sum = sum+matrix[i-1][j-1];
                
                sums[i][j] = sum + sums[i-1][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(sums==null)
            return -1;
        return sums[row2+1][col2+1]-sums[row2+1][col1] - sums[row1][col2+1] + sums[row1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

308 Range Sum Query 2D - Mutable

class NumMatrix {
    int[][] sums;
    int[][] matrix;
    public NumMatrix(int[][] matrix) {
        if(matrix==null || matrix.length==0 || matrix[0]==null || matrix[0].length==0)
            return;
        sums = new int[matrix.length+1][matrix[0].length+1];
        this.matrix = matrix;
        for(int i=1; i<=matrix.length; i++){
            int sum = 0;
            for(int j=1; j<=matrix[0].length; j++){
                sum = sum + matrix[i-1][j-1];
                sums[i][j] = sums[i-1][j] + sum;
            }
        }
    }
    
    public void update(int row, int col, int val) {
        if(sums==null)
            return;
        int delta = val - matrix[row][col];
        System.out.println(delta);
        matrix[row][col] = val;
        for(int i=row+1; i<sums.length; i++){
            for(int j=col+1; j<sums[0].length; j++){
                sums[i][j] = sums[i][j] + delta;
            }
        }
        
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(sums==null)
            return -1;
        return sums[row2+1][col2+1]+sums[row1][col1]-sums[row2+1][col1]-sums[row1][col2+1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * obj.update(row,col,val);
 * int param_2 = obj.sumRegion(row1,col1,row2,col2);
 */

基础九 子数组和前缀和

53. Maximum Subarray 找和最大的子数组

lt138 Subarray Sum

139. Subarray Sum Closest

121 Best Time to Buy and Sell Stock

lt405 Submatrix Sum

lt944 Maximum Submatrix

304 Range Sum Query 2D - Immutable

308 Range Sum Query 2D - Mutable

基础九子数组和前缀和