C ++中的K级数最大和

假设我们有一个整数数组arr和一个整数k，我们必须通过重复k次来更改该数组。因此，如果arr = [1，2]且k = 3，则修改后的数组将为[1、2、1、2、1、2]。

现在我们必须在修改后的数组中找到最大子数组总和。请注意，子数组的长度可以为0，在这种情况下，其总和为0。由于答案可能非常大，因此求模10 ^ 9 + 7的答案。

因此，如果输入像[1，-2,1]且k = 5，则结果将为2。

为了解决这个问题，我们将遵循以下步骤-

定义称为的方法getKadane()，它将采用数组，其工作方式类似于-
ret：= -inf，sum：= 0，ret和sum的所有值都是mod 10 ^ 9 + 7
对于范围从0到arr的i – 1

sum：= arr [i]和arr [i]的最大值+和
ret：=最大ret，总和

如果ret <0，则返回0，否则返回
定义称为的方法getSum()，它将采用数组，其工作方式类似于-
ret：= 0，ret的值为mod 10 ^ 9 + 7
对于范围从0到arr的i – 1

ret：= ret + arr [i]

返回ret
定义称为的方法getPrefix()，它将采用数组，其工作方式类似于-
ret：= -inf，sum：= 0，ret和sum的所有值都是mod 10 ^ 9 + 7
对于范围从0到arr的i – 1

sum：= sum + arr [i]
ret：= ret和sum的最大值

如果ret <0，则返回0，否则返回
定义称为的方法getSuffix()，它将采用数组，其工作方式类似于-
ret：= inf，sum：= 0，ret和sum的所有值均为mod 10 ^ 9 + 7
对于我在arr范围内的值– 1降至0

sum：= sum + arr [i]
ret：= ret和sum的最大值

如果ret <0，则返回0，否则返回
从主要方法中，执行以下操作-
kadane：= getKadane(arr)，sum：= getSum(arr)，前缀：= getPrefix(arr)，后缀：= getSuffix(arr)
如果k为1，则返回kadane
如果sum> 1，则返回（sum *(k-2)）+前缀+后缀和kadane的最大值
否则返回（prefix +后缀）和kadane的最大值

例子（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;
int add(lli a, lli b){
   return ((a % MOD) + (b % MOD)) % MOD;
}
int mul(lli a, lli b){
   return ((a % MOD) * (b % MOD)) % MOD;
}
class Solution {
   public:
   int getKadane(vector <int>& arr){
      int ret = INT_MIN;
      int sum = 0;
      for(int i = 0; i < arr.size(); i++){
         sum = max(arr[i], arr[i] + sum);
         ret = max(ret, sum);
         sum %= MOD;
         ret %= MOD;
      }
      return ret < 0? 0 : ret;
   }
   int getSum(vector <int>& arr){
      int ret = 0;
      for(int i = 0; i < arr.size(); i++){
         ret += arr[i];
         ret %= MOD;
      }
      return ret;
   }
   int getPrefix(vector <int>& arr){
      int ret = INT_MIN;
      int sum = 0;
      for(int i = 0; i <arr.size(); i++){
         sum += arr[i];
         sum %= MOD;
         ret = max(ret, sum);
         ret %= MOD;
      }
      return ret < 0 ? 0 : ret;
   }
   int getSuffix(vector <int>& arr){
      int sum = 0;
      int ret = INT_MIN;
      for(int i = arr.size() - 1; i >= 0 ; i--){
         sum += arr[i];
         ret = max(ret, sum);
         sum %= MOD;
         ret %= MOD;
      }
      return ret < 0 ? 0 : ret;
   }
   int kConcatenationMaxSum(vector<int>& arr, int k) {
      int kadane = getKadane(arr);
      int sum = getSum(arr);
      int prefix = getPrefix(arr);
      int suffix = getSuffix(arr);
      if(k == 1) return kadane;
      if(sum > 0){
         return max((int)mul((k-2) , sum) + prefix % MOD + suffix % MOD, kadane);
      } else {
         return max(add(prefix , suffix), kadane);
      }
   }
};
main(){
   vector<int> v1 = {1,-2,1};
   Solution ob;
   cout << (ob.kConcatenationMaxSum(v1, 5));
}

输入项

[1,-2,1]
5

输出结果

基础教程