Giả sử chúng ta có một mảng số nguyên arr và một số nguyên k, chúng ta phải thay đổi mảng nhân đôi nó k lần. Vì vậy, nếu arr =[1, 2] và k =3 thì mảng đã sửa đổi sẽ là [1, 2, 1, 2, 1, 2].
Bây giờ chúng ta phải tìm tổng mảng con tối đa trong mảng đã sửa đổi. Lưu ý rằng độ dài của mảng con có thể bằng 0 và tổng của nó trong trường hợp đó là 0. Vì câu trả lời có thể rất lớn, hãy tìm câu trả lời theo modulo 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là [1, -2,1] và k =5, thì kết quả sẽ là 2.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định phương thức được gọi là getKadane (), phương thức này sẽ nhận mảng, điều này sẽ hoạt động như -
-
ret:=-inf, sum:=0, tất cả các giá trị của ret và sum sẽ là mod 10 ^ 9 + 7
-
cho tôi trong phạm vi từ 0 đến kích thước của arr - 1
-
sum:=max of arr [i] và arr [i] + sum
-
ret:=max của ret, sum
-
-
nếu ret là <0 thì trả về 0, ngược lại thì ret
-
Xác định phương thức được gọi là getSum (), phương thức này sẽ nhận mảng, điều này sẽ hoạt động như -
-
ret:=0, Giá trị ret sẽ là mod 10 ^ 9 + 7
-
cho tôi trong phạm vi từ 0 đến kích thước của arr - 1
-
ret:=ret + arr [i]
-
-
trả lại ret
-
Xác định phương thức được gọi là getPrefix (), phương thức này sẽ nhận mảng, điều này sẽ hoạt động như -
-
ret:=-inf, sum:=0, tất cả các giá trị của ret và sum sẽ là mod 10 ^ 9 + 7
-
cho tôi trong phạm vi từ 0 đến kích thước của arr - 1
-
sum:=sum + arr [i]
-
ret:=max của ret và sum
-
-
nếu ret là <0 thì trả về 0, ngược lại thì ret
-
Xác định phương thức được gọi là getSuffix (), phương thức này sẽ nhận mảng, điều này sẽ hoạt động như -
-
ret:=inf, sum:=0, tất cả các giá trị của ret và sum sẽ là mod 10 ^ 9 + 7
-
cho tôi trong phạm vi kích thước arr - 1 xuống 0
-
sum:=sum + arr [i]
-
ret:=max của ret và sum
-
-
nếu ret là <0 thì trả về 0, ngược lại thì ret
-
Từ phương thức chính, thực hiện như sau -
-
kadane:=getKadane (arr), sum:=getSum (arr), tiền tố:=getPrefix (arr), hậu tố:=getSuffix (arr)
-
nếu k là 1, thì trả về kadane
-
nếu sum> 1, thì trả về giá trị max của (sum * (k - 2)) + tiền tố + hậu tố và kadane
-
nếu không thì trả về tối đa của (tiền tố + hậu tố) và kadane
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
[1,-2,1] 5
Đầu ra
2