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 – 1 크기의 i에 대해
- 합계 :=arr[i] 및 arr[i]의 최대값 + 합계
- ret :=ret의 최대값, 합계
ret가 <0이면 0을 반환하고 그렇지 않으면 ret
getSum()이라는 메서드를 정의합니다. 이것은 배열을 사용하며 다음과 같이 작동합니다. -
ret :=0, ret 값은 mod 10^9 + 7
이 됩니다.
범위 0에서 arr – 1 크기의 i에 대해
- 렛 :=렛 + arr[i]
리턴 렛
getPrefix()라는 메서드를 정의합니다. 이것은 배열을 사용하며 다음과 같이 작동합니다. -
ret :=-inf, sum :=0, ret 및 sum의 모든 값은 mod 10^9 + 7
이 됩니다.
범위 0에서 arr – 1 크기의 i에 대해
- 합계 :=합계 + arr[i]
- ret :=ret 및 합계의 최대값
ret가 <0이면 0을 반환하고 그렇지 않으면 ret
getSuffix()라는 메서드를 정의합니다. 이것은 배열을 사용하며 다음과 같이 작동합니다. -
ret :=inf, sum :=0, ret 및 sum의 모든 값은 mod 10^9 + 7
이 됩니다.
for i in 범위 크기 arr – 1에서 0까지
- 합계 :=합계 + arr[i]
- ret :=ret 및 합계의 최대값
ret가 <0이면 0을 반환하고 그렇지 않으면 ret
기본 방법에서 다음을 수행하십시오 -
kadane :=getKadane(arr), 합계 :=getSum(arr), 접두사 :=getPrefix(arr), 접미사 :=getSuffix(arr)
k가 1이면 kadane을 반환합니다.
합계> 1이면 (sum * (k - 2)) + 접두사 + 접미사 및 kadane의 최대값을 반환합니다.
그렇지 않으면 (접두사 + 접미사) 및 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

C++의 K-연결 최대 합

예시(C++)

입력

출력