dede电影网站源码,wordpress页面的设置,交互设计专业国内大学排名,网店代运营违法吗子数组最大累加和问题是一个非常经典的问题#xff0c;也比较简单。但是扩展出的问题很多#xff0c;在笔试、面试中特别常见#xff0c;扩展出的问题很多非常有趣#xff0c;解法也比较巧妙。 下面通过一些题目来加深理解。 题目一
测试链接#xff1a;https://leetcode…子数组最大累加和问题是一个非常经典的问题也比较简单。但是扩展出的问题很多在笔试、面试中特别常见扩展出的问题很多非常有趣解法也比较巧妙。 下面通过一些题目来加深理解。 题目一
测试链接https://leetcode.cn/problems/maximum-subarray/
分析这是一道常见且较为简单的题下面给出严格位置依赖和空间压缩的解法。代码如下。
class Solution {
public:int dp[100000];int maxSubArray(vectorint nums) {int length nums.size();int ans nums[0];dp[0] nums[0];for(int i 1;i length;i){dp[i] dp[i-1] 0 ? dp[i-1] nums[i] : nums[i];ans ans dp[i] ? ans : dp[i];}return dp[length-1];}
};
下面是空间压缩的解法。代码如下。
class Solution {
public:int maxSubArray(vectorint nums) {int length nums.size();int cur, last;int ans nums[0];last nums[0];for(int i 1;i length;i){cur last 0 ? last nums[i] : nums[i];ans ans cur ? ans : cur;last cur;}return ans;}
}; 题目二
测试链接https://leetcode.cn/problems/house-robber/
分析这相当于是一个不能取相邻数的最大数组累加和的题。可以构造二维dp数组dp[i][0]代表以i为结尾不偷下标为i的房屋的最大金额dp[i][1]代表以i为结尾偷下标为i的房屋的最大金额。代码如下。
class Solution {
public:int dp[100][2];int rob(vectorint nums) {int length nums.size();int ans nums[0];dp[0][0] 0;dp[0][1] nums[0];for(int i 1;i length;i){dp[i][0] dp[i-1][0] dp[i-1][1] ? dp[i-1][0] : dp[i-1][1];ans ans dp[i][0] ? ans : dp[i][0];dp[i][1] dp[i-1][0] nums[i];ans ans dp[i][1] ? ans : dp[i][1];}return ans;}
};
下面是空间压缩的解法。代码如下。
class Solution {
public:int rob(vectorint nums) {int length nums.size();int ans nums[0];int last_no 0, last_yes nums[0];int cur_no, cur_yes;for(int i 1;i length;i){cur_no last_no last_yes ? last_no : last_yes;ans ans cur_no ? ans : cur_no;cur_yes last_no nums[i];ans ans cur_yes ? ans : cur_yes;last_no cur_no;last_yes cur_yes;}return ans;}
}; 题目三
测试链接https://leetcode.cn/problems/maximum-sum-circular-subarray/
分析对于环形数组求子数组的最大和有两种情况一种是最大子数组就是非环形数组求最大子数组的结果另一种是子数组跨过了开头和结尾。对于第一种情况正常求数组的最大子数组即可。对于第二种情况只需求数组的最小子数组然后用数组的总和减去最小子数组。两种情况取最大值即是答案。代码如下。
class Solution {
public:int dp1[30001];int dp2[30001];int maxSubarraySumCircular(vectorint nums) {int length nums.size();int ans1 nums[0], ans2 nums[0], all nums[0];dp1[0] nums[0];dp2[0] nums[0];for(int i 1;i length;i){all nums[i];dp1[i] dp1[i-1] 0 ? dp1[i-1] nums[i] : nums[i];ans1 ans1 dp1[i] ? ans1 : dp1[i];dp2[i] dp2[i-1] 0 ? nums[i] : dp2[i-1] nums[i];ans2 ans2 dp2[i] ? ans2 : dp2[i];}return ans2 all ? ans1 : ans1 all - ans2 ? ans1 : all - ans2;}
};
下面是空间压缩的解法。代码如下。
class Solution {
public:int last_1, cur_1;int last_2, cur_2;int maxSubarraySumCircular(vectorint nums) {int length nums.size();int ans1 nums[0], ans2 nums[0], all nums[0];last_1 nums[0];last_2 nums[0];for(int i 1;i length;i){all nums[i];cur_1 last_1 0 ? last_1 nums[i] : nums[i];ans1 ans1 cur_1 ? ans1 : cur_1;cur_2 last_2 0 ? nums[i] : last_2 nums[i];ans2 ans2 cur_2 ? ans2 : cur_2;last_1 cur_1;last_2 cur_2;}return ans2 all ? ans1 : ans1 all - ans2 ? ans1 : all - ans2;}
};题目四
测试链接https://leetcode.cn/problems/house-robber-ii/
分析对于这种环形的情况依然是分了两种情况第一种情况是不偷下标为0的房子第二种情况是偷下标为0的房子。这两种情况最后求出来四个值取最大即是答案。代码如下。
class Solution {
public:int dp1[101][2];int dp2[101][2];int get_max(int a, int b, int c, int d){int ans a;ans ans b ? ans : b;ans ans c ? ans : c;ans ans d ? ans : d;return ans;}int rob(vectorint nums) {int length nums.size();if(length 1){return nums[0];}if(length 2){return nums[0] nums[1] ? nums[0] : nums[1];}dp1[1][0] 0;dp1[1][1] nums[1];for(int i 2;i length;i){dp1[i][0] dp1[i-1][0] dp1[i-1][1] ? dp1[i-1][0] : dp1[i-1][1];dp1[i][1] dp1[i-1][0] nums[i];}dp2[2][0] 0;dp2[2][1] nums[2];for(int i 3;i length-1;i){dp2[i][0] dp2[i-1][0] dp2[i-1][1] ? dp2[i-1][0] : dp2[i-1][1];dp2[i][1] dp2[i-1][0] nums[i];}return get_max(dp1[length-1][0], dp1[length-1][1], dp2[length-2][0]nums[0], dp2[length-2][1]nums[0]);}
};
下面是空间压缩的版本。代码如下。
class Solution {
public:int last_1_no, last_1_yes, cur_1_no, cur_1_yes;int last_2_no, last_2_yes, cur_2_no, cur_2_yes;int get_max(int a, int b, int c, int d){int ans a;ans ans b ? ans : b;ans ans c ? ans : c;ans ans d ? ans : d;return ans;}int rob(vectorint nums) {int length nums.size();if(length 1){return nums[0];}if(length 2){return nums[0] nums[1] ? nums[0] : nums[1];}if(length 3){return nums[0] nums[1] ? nums[0] nums[2] ? nums[0] : nums[2] : nums[1] nums[2] ? nums[1] : nums[2];}last_1_no 0;last_1_yes nums[1];for(int i 2;i length;i){cur_1_no last_1_no last_1_yes ? last_1_no : last_1_yes;cur_1_yes last_1_no nums[i];last_1_no cur_1_no;last_1_yes cur_1_yes;}last_2_no 0;last_2_yes nums[2];for(int i 3;i length-1;i){cur_2_no last_2_no last_2_yes ? last_2_no : last_2_yes;cur_2_yes last_2_no nums[i];last_2_no cur_2_no;last_2_yes cur_2_yes;}return get_max(last_1_no, last_1_yes, last_2_nonums[0], last_2_yesnums[0]);}
}; 题目五
测试链接https://leetcode.cn/problems/house-robber-iv/
分析这道题可以想到二分答案法。因为窃取能力的范围是有限的只需要使用二分搜索对窃取能力是否能偷盗至少k间房屋进行判断即可得到最小窃取能力。代码如下。
class Solution {
public:int last_no, last_yes, cur_no, cur_yes;int f(int ability, vectorint nums, int length){last_no 0;last_yes nums[0] ability ? 1 : 0;for(int i 1;i length;i){cur_no last_no last_yes ? last_no : last_yes;cur_yes nums[i] ability ? last_no 1 : last_no;last_no cur_no;last_yes cur_yes; }return last_no last_yes ? last_no : last_yes;}int get_max(vectorint nums, int length){int ans nums[0];for(int i 1;i length;i){ans ans nums[i] ? ans : nums[i];}return ans;}int minCapability(vectorint nums, int k) {int length nums.size();int l 0, r, middle, ans;r get_max(nums, length);while (l r){middle l (r - l) / 2;if(f(middle, nums, length) k){r middle - 1;ans middle;}else{l middle 1;}}return ans;}
}; 题目六
测试链接https://leetcode.cn/problems/max-submatrix-lcci/
分析这个就是子数组求最大累加和拓展了一个维度。首先对于不同数量不同行的组合在相同下标上的值求和得到一个一维数组。对这个一维数组求子数组最大累加和找到最大的答案记录坐标即可。遍历即可得到答案。代码如下。
class Solution {
public:int last, last_start, cur, cur_start, ans, ans_start, ans_end;int f(vectorint nums, int length){last nums[0];last_start 0;ans nums[0];ans_start 0;ans_end 0;for(int i 1;i length;i){cur last 0 ? last nums[i] : nums[i];cur_start last 0 ? last_start : i;if(cur ans){ans cur;ans_start cur_start;ans_end i;}last cur;last_start cur_start;}return ans;}vectorint getMaxMatrix(vectorvectorint matrix) {int r1, c1, r2, c2;vectorint Ans;Ans.assign(4, 0);int maxValue (1 31);int value;int row matrix.size();int column matrix[0].size();int add;vectorint temp;temp.assign(column, 0);for(int i 0;i row;i){for(int j i;j row;j){for(int index 0;index column;index){add 0;for(int begin i;begin j;begin){add matrix[begin][index];}temp[index] add;}value f(temp, column);if(value maxValue){maxValue value;r1 i;c1 ans_start;r2 j;c2 ans_end;}}}Ans[0] r1;Ans[1] c1;Ans[2] r2;Ans[3] c2;return Ans;}
}; 题目七
测试链接https://leetcode.cn/problems/maximum-product-subarray/
分析因为数组中的值有正有负所以对于dp数组需要求得以下标i为结尾的最大值和最小值。下面直接给出空间压缩的版本。代码如下。
class Solution {
public:int maxProduct(vectorint nums) {int last_max, last_min, cur_max, cur_min;int length nums.size();int ans nums[0];last_min nums[0];last_max nums[0];for(int i 1;i length;i){if(nums[i] 0){cur_max 0;cur_min 0;}else{if(nums[i] 0){cur_max last_min 0 ? last_min * nums[i] : nums[i];cur_min last_max 0 ? last_max * nums[i] : nums[i];}else{cur_max last_max 0 ? last_max * nums[i] : nums[i];cur_min last_min 0 ? last_min * nums[i] : nums[i];}}ans ans cur_max ? ans : cur_max;last_max cur_max;last_min cur_min;}return ans;}
}; 题目八 子序列累加和必须被7整除的最大累加和 给定一个非负数组nums 可以任意选择数字组成子序列但是子序列的累加和必须被7整除 返回最大累加和 分析dp[i][j]代表以前i个数除以7余数为j的最大累加和。代码如下。
class Solution {
public:int dp[10000][7] {0};int get_max(vectorint nums) {int length nums.size();int cur;for(int i 1;i length;i){cur nums[i-1] % 7;for(int j 0;j 7;j){dp[i][j] dp[i-1][j];if(cur j){dp[i][j] dp[i][j] dp[i-1][j-cur] nums[i-1] ? dp[i][j] : dp[i-1][j-cur] nums[i-1];}else{dp[i][j] dp[i][j] dp[i-1][j-cur7] nums[i-1] ? dp[i][j] : dp[i-1][j-cur7] nums[i-1];}}}return dp[length][0];}
}; 题目九 魔法卷轴 给定一个数组nums其中可能有正、负、0 每个魔法卷轴可以把nums中连续的一段全变成0 你希望数组整体的累加和尽可能大 卷轴使不使用、使用多少随意但一共只有2个魔法卷轴 请返回数组尽可能大的累加和 分析这道题可以将情况拆开来看对于不使用、使用1次、使用2次分别求出数组累加和相比较即可得出最大值。不使用时就是简单的求和使用1次可以看成是求出数组中子数组最小累加和如果大于等于0代表数组全部为非负数故直接返回数组累加和即可如果最小累加和等于数组累加和代表数组全是负数故直接返回0即可。使用2次就需要在找到一个次小累加和因为次小累加和和最小累加和的范围一定是不重合的所以对于次小累加和的寻找可以看成是在最小累加和范围之外的左右两边数组中寻找最小累加和取最小的即可得到次小累加和如果次小累加和大于等于0代表只需要使用1次否则需要使用2次。代码如下。
class Solution {
public:int get_max(vectorint nums) {int all 0;int last, last_start, cur, cur_start;int min_value, min_start, min_end;int length nums.size();for(int i 0;i length;i){all nums[i];}min_value nums[0];last nums[0];last_start 0;min_start 0;min_end 0;for(int i 1;i length;i){cur last 0 ? last : last nums[i];cur_start last 0 ? i : last_start;if(cur min_value){min_value cur;min_start cur_start;min_end i;}last cur;last_start cur_start;}if(min_value 0){return all;}if(min_value all){return 0;}int minest min_value;int start 0, end min_start-1, temp1 0, temp2 0;if(start end){min_value nums[start];last nums[start];for(int i start;i end;i){cur last 0 ? nums[i] : last nums[i];min_value min_value cur ? min_value : cur;}temp1 min_value;}start min_end1;end length-1;if(start end){min_value nums[start];last nums[start];for(int i start;i end;i){cur last 0 ? nums[i] : last nums[i];min_value min_value cur ? min_value : cur;}temp2 min_value;}int tmp temp1 temp2 ? temp1 : temp2;if(tmp 0){return all - minest;}return all - minest - tmp;}
}; 题目十
测试链接https://leetcode.cn/problems/maximum-sum-of-3-non-overlapping-subarrays/
分析这道题思路是构造前缀后缀信息在数组中截取一个长度为k的子数组然后用前缀信息和后缀信息求得3个子数组的和遍历数组即可求得最大值。prefix[i]代表以下标i结尾时长度为k的最大累加和子数组的开始下标suffix[i]代表以下标i为开头时长度为k的最大累加和子数组的开始下标。代码如下。
class Solution {
public:int Sum[20001];int prefix[20001];int suffix[20001];vectorint maxSumOfThreeSubarrays(vectorint nums, int k) {int length nums.size();int window 0;int ans 0;vectorint Ans;Ans.assign(3, 0);int index1, index2, index3;for(int i 0;i k;i){window nums[i];}Sum[0] window;for(int i 1;i length-k1;i){window - nums[i-1];window nums[ik-1];Sum[i] window;}prefix[k-1] 0;for(int i k;i length-k1;i){prefix[i] Sum[prefix[i-1]] Sum[i-k1] ? prefix[i-1] : i-k1;}suffix[length-k] length-k;for(int i length-k-1;i 0;--i){suffix[i] Sum[suffix[i1]] Sum[i] ? suffix[i1] : i;}for(int i k;i length-2*k1;i){if(ans Sum[i] Sum[prefix[i-1]] Sum[suffix[ik]]){ans Sum[i] Sum[prefix[i-1]] Sum[suffix[ik]];index1 prefix[i-1];index2 i;index3 suffix[ik];}}Ans[0] index1;Ans[1] index2;Ans[2] index3;return Ans;}
}; 题目十一 可以翻转1次的情况下子数组最大累加和 给定一个数组nums 现在允许你随意选择数组连续一段进行翻转也就是子数组逆序的调整 比如翻转[1,2,3,4,5,6]的[2~4]范围得到的是[1,2,5,4,3,6] 返回必须随意翻转1次之后子数组的最大累加和 分析可以看出翻转其实是选定一个边界边界左边的进行翻转边界右边的不动或者左边不动右边翻转。这样只需要得到边界左边以边界为结尾的子数组最大累加和以及边界右边以边界为开头的子数组最大累加和相加即是这个边界的答案。遍历数组即可得到子数组的最大累加和。代码如下。
class Solution {
public:int get_reverse_max(vectorint nums) {int dp1[10000] {0};int dp2[10000] {0};int ans;int length nums.size();dp1[0] nums[0];for(int i 1;i length;i){dp1[i] dp1[i-1] 0 ? dp1[i-1] nums[i] : nums[i];}dp2[length-1] nums[length-1];for(int i length-2;i 0;--i){dp2[i] dp2[i1] 0 ? dp2[i1] nums[i] : nums[i];}ans dp2[0];int front_max dp1[0];for(int i 1;i length;i){front_max front_max dp1[i-1] ? front_max : dp1[i-1];ans ans front_max dp2[i] ? ans : front_max dp2[i];}return ans;}
}; 题目十二 删掉1个数字后长度为k的子数组最大累加和 给定一个数组nums求必须删除一个数字后的新数组中 长度为k的子数组最大累加和删除哪个数字随意 分析这道题可以理解为对于每一个长度为k1的子数组删除这这个子数组中的最小值从每一个长度为k1的子数组中求得结果。因为子数组要减去子数组范围内的最小值所以可以采用单调队列。代码如下。
class Solution {
public:int get_delete1_max(vectorint nums, int k) {int length nums.size();if(length k){return 0;}vectorint window;window.assign(length, 0);int l 0;int r 0;long sum 0;int ans (1 31);for(int i 0;i length;i){while (l r nums[window[r-1]] nums[i]){--r;}window[r] i;sum nums[i];if(i k){ans ans sum - nums[window[l]] ? ans : sum - nums[window[l]];if(window[l] i-k){l;}sum - nums[i-k];}}return ans;}
};
