网站如何创建首页,100平米全包装修价格,wordpress 封ip段,成都网站建设cdsqywl1749. 任意子数组和的绝对值的最大值
给你一个整数数组 nums 。一个子数组 [numsl, numsl1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl numsl1 ... numsr-1 numsr) 。
请你找出 nums 中 和的绝对值 最大的任意子数组#xff08;可能为空#xff09;#xff0c…1749. 任意子数组和的绝对值的最大值
给你一个整数数组 nums 。一个子数组 [numsl, numsl1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl numsl1 ... numsr-1 numsr) 。
请你找出 nums 中 和的绝对值 最大的任意子数组可能为空并返回该 最大值 。
abs(x) 定义如下
如果 x 是负整数那么 abs(x) -x 。如果 x 是非负整数那么 abs(x) x 。
数据范围
1 nums.length 105-104 nums[i] 104
分析
最大子数组和的变式可以求处最大子数组和和最小子数组和然后取绝对值的max
代码
typedef long long LL;
class Solution {
public:const static int N 1e5 5, INF 0x3f3f3f3f;int dp1[N], dp2[N];int maxAbsoluteSum(vectorint nums) {int n nums.size();int res 0;dp1[0] -INF;dp2[0] INF; for(int i 1; i n; i ) {dp1[i] max(nums[i - 1], dp1[i - 1] nums[i - 1]);dp2[i] min(nums[i - 1], dp2[i - 1] nums[i - 1]);res max(res, abs(dp1[i]));res max(res, abs(dp2[i]));}return res;}
};1191. K 次串联后最大子数组之和
给定一个整数数组 arr 和一个整数 k 通过重复 k 次来修改数组。
例如如果 arr [1, 2] k 3 那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。
返回修改后的数组中的最大的子数组之和。注意子数组长度可以是 0在这种情况下它的总和也是 0。
由于 结果可能会很大需要返回的 109 7 的 模 。
数据范围
1 arr.length 1051 k 105-104 arr[i] 104
分析
分类讨论两种情况对于k1的情况直接在长度为n的数组上做一次子数组最大和对于k1的情况可能会出现起点和终点不在同一个区间内因此需要对数组进行复制而对于中间是否需要加上一整段区间只需要看数组的和是否为正数若是正数则一定可以将整段区间插入到起点和终点之间。
代码
typedef long long LL;
class Solution {
public:const static LL N 1e5 5, INF 0x3f3f3f3f, mod (LL)1e9 7;LL res 0;LL dp[2 * N];LL kConcatenationMaxSum(vectorint arr, int k) {int n arr.size();LL sum 0;for(int i 0; i n; i ) {sum arr[i];sum % mod;}dp[0] 0;for(int i 1; i n * (k 1 ? 2 : 1); i ) {dp[i] max((LL)0, dp[i - 1] (LL)arr[(i - 1) % n]);if(sum 0 k 2) res max(res, dp[i] sum * (k - 2) % mod);else res max(res, dp[i]);dp[i] % mod;res % mod;}return res % mod;}
};918. 环形子数组的最大和
给定一个长度为 n 的环形整数数组 nums 返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上 nums[i] 的下一个元素是 nums[(i 1) % n] nums[i] 的前一个元素是 nums[(i - 1 n) % n] 。
子数组 最多只能包含固定缓冲区 nums中的每个元素一次。形式上对于子数组 nums[i], nums[i 1], ..., nums[j] 不存在 i k1, k2 j 其中 k1 % n k2 % n 。
数据范围
n nums.length1 n 3 * 104-3 * 104 nums[i] 3 * 104
分析
令dp[i]表示以i结尾的最大子数组和同时用len[i]记录长度对于环形我们可以开两倍数组将首位相接然后跑一边最大子数组和并记录长度若长度大于n则说明需要删去首部一些点由于我们已经记录了子数组的长度所以可以轻松找到这段子数组的开头之后找到前缀和小于0的最小值mins将dp[i]减去mins同时更新len即可
代码
class Solution {
public:const static int N 3e4 5, INF 0x3f3f3f3f;int dp[2 * N];int len[2 * N];int maxSubarraySumCircular(vectorint nums) {int n nums.size();int res -INF;dp[0] -INF;for(int i 1; i 2 * n; i ) {if(dp[i - 1] nums[(i - 1) % n] nums[(i - 1) % n]) {dp[i] dp[i - 1] nums[(i - 1) % n];len[i] len[i - 1] 1;} else {dp[i] nums[(i - 1) % n];len[i] 1;}if(len[i] n) {int t len[i];int last i - t 1;while(i - last 1 n) {dp[i] - nums[(last - 1) % n];last ;}int minsum 0, sum 0;int pos last - 1;for(int k last; k i; k ) {sum nums[(k - 1) % n];if(minsum sum) {minsum sum;pos k;}}len[i] i - pos;dp[i] - minsum;}res max(res, dp[i]);}return res;}
};
