class070 子数组最大累加和问题与扩展-上【算法】

package class070;
// 子数组最大累加和
// 给你一个整数数组 nums
// 返回非空子数组的最大累加和
// 测试链接 : https://leetcode.cn/problems/maximum-subarray/
public class Code01_MaximumSubarray {
  // 动态规划
  public static int maxSubArray1(int[] nums) {
    int n = nums.length;
    // dp[i] : 子数组必须以i位置的数做结尾，往左能延伸出来的最大累加和
    int[] dp = new int[n];
    dp[0] = nums[0];
    int ans = nums[0];
    for (int i = 1; i < n; i++) {
      dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
      ans = Math.max(ans, dp[i]);
    }
    return ans;
  }
  // 空间压缩
  public static int maxSubArray2(int[] nums) {
    int n = nums.length;
    int ans = nums[0];
    for (int i = 1, pre = nums[0]; i < n; i++) {
      pre = Math.max(nums[i], pre + nums[i]);
      ans = Math.max(ans, pre);
    }
    return ans;
  }
  // 如下代码为附加问题的实现
  // 子数组中找到拥有最大累加和的子数组
  // 并返回如下三个信息:
  // 1) 最大累加和子数组的开头left
  // 2) 最大累加和子数组的结尾right
  // 3) 最大累加和子数组的累加和sum
  // 如果不止一个子数组拥有最大累加和，那么找到哪一个都可以
  public static int left;
  public static int right;
  public static int sum;
  // 找到拥有最大累加和的子数组
  // 更新好全局变量left、right、sum
  // 上游调用函数可以直接使用这三个变量
  // 相当于返回了三个值
  public static void extra(int[] nums) {
    sum = Integer.MIN_VALUE;
    for (int l = 0, r = 0, pre = Integer.MIN_VALUE; r < nums.length; r++) {
      if (pre >= 0) {
        // 吸收前面的累加和有利可图
        // 那就不换开头
        pre += nums[r];
      } else {
        // 吸收前面的累加和已经无利可图
        // 那就换开头
        pre = nums[r];
        l = r;
      }
      if (pre > sum) {
        sum = pre;
        left = l;
        right = r;
      }
    }
  }
}

package class070;
// 数组中不能选相邻元素的最大累加和
// 给定一个数组，可以随意选择数字
// 但是不能选择相邻的数字，返回能得到的最大累加和
// 测试链接 : https://leetcode.cn/problems/house-robber/
public class Code02_HouseRobber {
  // 动态规划
  public static int rob1(int[] nums) {
    int n = nums.length;
    if (n == 1) {
      return nums[0];
    }
    if (n == 2) {
      return Math.max(nums[0], nums[1]);
    }
    // dp[i] : nums[0...i]范围上可以随意选择数字，但是不能选相邻数，能得到的最大累加和
    int[] dp = new int[n];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
      dp[i] = Math.max(dp[i - 1], Math.max(nums[i], dp[i - 2] + nums[i]));
    }
    return dp[n - 1];
  }
  // 空间压缩
  public static int rob2(int[] nums) {
    int n = nums.length;
    if (n == 1) {
      return nums[0];
    }
    if (n == 2) {
      return Math.max(nums[0], nums[1]);
    }
    int prepre = nums[0];
    int pre = Math.max(nums[0], nums[1]);
    for (int i = 2, cur; i < n; i++) {
      cur = Math.max(pre, Math.max(nums[i], prepre + nums[i]));
      prepre = pre;
      pre = cur;
    }
    return pre;
  }
}

package class070;
// 环形数组的子数组最大累加和
// 给定一个数组nums，长度为n
// nums是一个环形数组，下标0和下标n-1是连在一起的
// 返回环形数组中，子数组最大累加和
// 测试链接 : https://leetcode.cn/problems/maximum-sum-circular-subarray/
public class Code03_MaximumSumCircularSubarray {
  public static int maxSubarraySumCircular(int[] nums) {
    int n = nums.length, all = nums[0], maxsum = nums[0], minsum = nums[0];
    for (int i = 1, maxpre = nums[0], minpre = nums[0]; i < n; i++) {
      all += nums[i];
      maxpre = Math.max(nums[i], nums[i] + maxpre);
      maxsum = Math.max(maxsum, maxpre);
      minpre = Math.min(nums[i], nums[i] + minpre);
      minsum = Math.min(minsum, minpre);
    }
    // 1) maxsum
    // 2) all - minsum
    return all == minsum ? maxsum : Math.max(maxsum, all - minsum);
  }
}

package class070;
// 环形数组中不能选相邻元素的最大累加和
// 给定一个数组nums，长度为n
// nums是一个环形数组，下标0和下标n-1是连在一起的
// 可以随意选择数字，但是不能选择相邻的数字
// 返回能得到的最大累加和
// 测试链接 : https://leetcode.cn/problems/house-robber-ii/
public class Code04_HouseRobberII {
  public static int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) {
      return nums[0];
    }
    return Math.max(best(nums, 1, n - 1), nums[0] + best(nums, 2, n - 2));
  }
  // nums[l....r]范围上，没有环形的概念
  // 返回 : 可以随意选择数字，但不能选择相邻数字的情况下，最大累加和
  public static int best(int[] nums, int l, int r) {
    if (l > r) {
      return 0;
    }
    if (l == r) {
      return nums[l];
    }
    if (l + 1 == r) {
      return Math.max(nums[l], nums[r]);
    }
    int prepre = nums[l];
    int pre = Math.max(nums[l], nums[l + 1]);
    for (int i = l + 2, cur; i <= r; i++) {
      cur = Math.max(pre, nums[i] + Math.max(0, prepre));
      prepre = pre;
      pre = cur;
    }
    return pre;
  }
}

package class070;
// 打家劫舍 IV
// 沿街有一排连续的房屋。每间房屋内都藏有一定的现金
// 现在有一位小偷计划从这些房屋中窃取现金
// 由于相邻的房屋装有相互连通的防盗系统，所以小偷不会窃取相邻的房屋
// 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额
// 给你一个整数数组 nums 表示每间房屋存放的现金金额
// 第i间房屋中放有nums[i]的钱数
// 另给你一个整数k，表示小偷需要窃取至少 k 间房屋
// 返回小偷需要的最小窃取能力值
// 测试链接 : https://leetcode.cn/problems/house-robber-iv/
public class Code05_HouseRobberIV {
  public static int minCapability(int[] nums, int k) {
    int n = nums.length, l = nums[0], r = nums[0];
    for (int i = 1; i < n; i++) {
      l = Math.min(l, nums[i]);
      r = Math.max(r, nums[i]);
    }
    // l....r
    int m, ans = 0;
    while (l <= r) {
      m = (l + r) / 2;
      if (mostRob1(nums, n, m) >= k) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
  // 盗贼能力为ability时
  // 返回盗贼最多能窃取多少间房屋
  // 注意限制 : 不能窃取相邻房屋
  public static int mostRob1(int[] nums, int n, int ability) {
    if (n == 1) {
      return nums[0] <= ability ? 1 : 0;
    }
    if (n == 2) {
      return (nums[0] <= ability || nums[1] <= ability) ? 1 : 0;
    }
    int[] dp = new int[n];
    dp[0] = nums[0] <= ability ? 1 : 0;
    dp[1] = (nums[0] <= ability || nums[1] <= ability) ? 1 : 0;
    for (int i = 2; i < n; i++) {
      dp[i] = Math.max(dp[i - 1], (nums[i] <= ability ? 1 : 0) + dp[i - 2]);
    }
    return dp[n - 1];
  }
  // 继续空间压缩优化
  public static int mostRob2(int[] nums, int n, int ability) {
    if (n == 1) {
      return nums[0] <= ability ? 1 : 0;
    }
    if (n == 2) {
      return (nums[0] <= ability || nums[1] <= ability) ? 1 : 0;
    }
    int prepre = nums[0] <= ability ? 1 : 0;
    int pre = (nums[0] <= ability || nums[1] <= ability) ? 1 : 0;
    for (int i = 2, cur; i < n; i++) {
      cur = Math.max(pre, (nums[i] <= ability ? 1 : 0) + prepre);
      prepre = pre;
      pre = cur;
    }
    return pre;
  }
  // 继续贪心优化
  public static int mostRob3(int[] nums, int n, int ability) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
      if (nums[i] <= ability) {
        ans++;
        i++;
      }
    }
    return ans;
  }
}

package class070;
import java.util.Arrays;
// 子矩阵最大累加和问题
// 给定一个二维数组grid，找到其中子矩阵的最大累加和
// 返回拥有最大累加和的子矩阵左上角和右下角坐标
// 如果有多个子矩阵都有最大累加和，返回哪一个都可以
// 测试链接 : https://leetcode.cn/problems/max-submatrix-lcci/
public class Code06_MaximumSubmatrix {
  // 如果行和列的规模都是n，时间复杂度O(n^3)，最优解了
  public static int[] getMaxMatrix(int[][] grid) {
    int n = grid.length;
    int m = grid[0].length;
    int max = Integer.MIN_VALUE;
    int a = 0, b = 0, c = 0, d = 0;
    int[] nums = new int[m];
    for (int up = 0; up < n; up++) {
      Arrays.fill(nums, 0);
      for (int down = up; down < n; down++) {
        // 如下代码就是题目1的附加问题 :
        // 子数组中找到拥有最大累加和的子数组
        for (int l = 0, r = 0, pre = Integer.MIN_VALUE; r < m; r++) {
          nums[r] += grid[down][r];
          if (pre >= 0) {
            pre += nums[r];
          } else {
            pre = nums[r];
            l = r;
          }
          if (pre > max) {
            max = pre;
            a = up;
            b = l;
            c = down;
            d = r;
          }
        }
      }
    }
    return new int[] { a, b, c, d };
  }
}