class070 子數組最大累加和問題與擴展-上【算法】

在這里插入圖片描述

code1 53. 最大子數組和

// 累加和最大子數組和
// 給你一個整數數組 nums
// 請你找出一個具有最大累加和的非空子數組
// 返回其最大累加和
// 測試鏈接 : https://leetcode.cn/problems/maximum-subarray/

dp[i]：以i結尾的子數組[…i]的最大累加和
(1) nums[i] (2) dp[i-1]+nums[i] 二者取最大的
返回Max(dp[…])

code1 動態規劃
code2 空間壓縮

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;}}}}

code2 198. 打家劫舍

// 數組中不能選相鄰元素的最大累加和
// 給定一個數組，可以隨意選擇數字
// 但是不能選擇相鄰的數字，返回能得到的最大累加和
// 測試鏈接 : https://leetcode.cn/problems/house-robber/

dp[i]：表示[0…i]這個范圍上不能選相鄰元素的最大累加和

不要[i]，dp[i-1]
要[i] a.nums[i] b.dp[i-2]+nums[i]

code1 動態規劃
code2 空間壓縮

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;}}

code3 918. 環形子數組的最大和

// 環形數組的子數組最大累加和
// 給定一個數組nums，長度為n
// nums是一個環形數組，下標0和下標n-1是連在一起的
// 返回環形數組中，子數組最大累加和
// 測試鏈接 : https://leetcode.cn/problems/maximum-sum-circular-subarray/

(1) 答案不被隔斷，同1普通數組，最大累加和maxSum
(2) 答案被隔斷，整體累加和all-最小累加和minSum
兩者取較大即為答案

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 - minsumreturn all == minsum ? maxsum : Math.max(maxsum, all - minsum);}}

code4 213. 打家劫舍 II

// 環形數組中不能選相鄰元素的最大累加和
// 給定一個數組nums，長度為n
// nums是一個環形數組，下標0和下標n-1是連在一起的
// 可以隨意選擇數字，但是不能選擇相鄰的數字
// 返回能得到的最大累加和
// 測試鏈接 : https://leetcode.cn/problems/house-robber-ii/

思路：
不要[0]位置 [1…n-1]
要[0]位置 nums[0] + [2…n-2]

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;}}

code5 2560. 打家劫舍 IV

// 打家劫舍 IV
// 沿街有一排連續的房屋。每間房屋內都藏有一定的現金
// 現在有一位小偷計劃從這些房屋中竊取現金
// 由于相鄰的房屋裝有相互連通的防盜系統，所以小偷不會竊取相鄰的房屋
// 小偷的竊取能力定義為他在竊取過程中能從單間房屋中竊取的最大金額
// 給你一個整數數組 nums 表示每間房屋存放的現金金額
// 第i間房屋中放有nums[i]的錢數
// 另給你一個整數k，表示小偷需要竊取至少 k 間房屋
// 返回小偷需要的最小竊取能力值
// 測試鏈接 : https://leetcode.cn/problems/house-robber-iv/

二分答案法
能力[min,max]有單調性
布爾函數判斷能力值給定，是否能偷夠k間

dp[i]：[0…i]范圍上不偷相鄰房間并且有能力要求的最大間數

不偷[i]，dp[i-1]
能力大于[i]，偷[i] dp[i-2]+1
偷不了[i] dp[i-2]

貪心優化：
能偷就偷，偷了就跳過，
盡早偷，留下更大的區間

code1 動態規劃
code2 空間壓縮
code3 貪心優化

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....rint 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;}}

code6 面試題 17.24. 最大子矩陣

// 子矩陣最大累加和問題
// 給定一個二維數組grid，找到其中子矩陣的最大累加和
// 返回擁有最大累加和的子矩陣左上角和右下角坐標
// 如果有多個子矩陣都有最大累加和，返回哪一個都可以
// 測試鏈接 : https://leetcode.cn/problems/max-submatrix-lcci/

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 };}}