สมมติว่าเรามีอาร์เรย์จำนวนเต็ม 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
-
sum :=สูงสุดของ arr[i] และ arr[i] + ผลรวม
-
ret :=สูงสุดของ ret, ผลรวม
-
-
ถ้า ret คือ <0 ให้คืนค่า 0 มิฉะนั้น ret
-
กำหนดวิธีการที่เรียกว่า getSum() ซึ่งจะใช้อาร์เรย์ ซึ่งจะทำงานเหมือน −
-
ret :=0, ค่า ret จะเป็น mod 10^9 + 7
-
สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ arr – 1
-
ret :=ret + arr[i]
-
-
รีเทิร์น
-
กำหนดเมธอดที่เรียกว่า getPrefix() ซึ่งจะใช้อาร์เรย์ ซึ่งจะทำงานเหมือน −
-
ret :=-inf, sum :=0, ค่า ret และ sum ทั้งหมดจะเป็น mod 10^9 + 7
-
สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ arr – 1
-
sum :=sum + arr[i]
-
ret :=สูงสุดของ ret และผลรวม
-
-
ถ้า ret คือ <0 ให้คืนค่า 0 มิฉะนั้น ret
-
กำหนดวิธีการที่เรียกว่า getSuffix() ซึ่งจะใช้อาร์เรย์ ซึ่งจะทำงานเหมือน −
-
ret :=inf, sum :=0, ค่า ret และ sum ทั้งหมดจะเป็น mod 10^9 + 7
-
สำหรับฉันในขนาดช่วงของ arr – 1 ลงไปที่ 0
-
sum :=sum + arr[i]
-
ret :=สูงสุดของ ret และผลรวม
-
-
ถ้า ret คือ <0 ให้คืนค่า 0 มิฉะนั้น ret
-
จากวิธีหลัก ให้ทำดังนี้ −
-
kadane :=getKadane(arr), sum :=getSum(arr), คำนำหน้า :=getPrefix(arr), suffix :=getSuffix(arr)
-
ถ้า k เป็น 1 ให้คืนค่า kadane
-
ถ้า sum> 1 ให้คืนค่า max ของ (sum * (k - 2)) + prefix + suffix and 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
ผลลัพธ์
2
