資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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 的所有值都將取模 10^9 + 7
對於 i 從 0 到 arr 的大小 - 1
sum := arr[i] 和 arr[i] + sum 的最大值
ret := ret 和 sum 的最大值
如果 ret < 0，則返回 0，否則返回 ret
定義一個名為 getSum() 的方法，它將接收陣列作為引數，其工作原理如下：
ret := 0，ret 的值將取模 10^9 + 7
對於 i 從 0 到 arr 的大小 - 1
ret := ret + arr[i]
返回 ret
定義一個名為 getPrefix() 的方法，它將接收陣列作為引數，其工作原理如下：
ret := -inf，sum := 0，ret 和 sum 的所有值都將取模 10^9 + 7
對於 i 從 0 到 arr 的大小 - 1
sum := sum + arr[i]
ret := ret 和 sum 的最大值
如果 ret < 0，則返回 0，否則返回 ret
定義一個名為 getSuffix() 的方法，它將接收陣列作為引數，其工作原理如下：
ret := inf，sum := 0，ret 和 sum 的所有值都將取模 10^9 + 7
對於 i 從 arr 的大小 - 1 到 0
sum := sum + arr[i]
ret := ret 和 sum 的最大值
如果 ret < 0，則返回 0，否則返回 ret
從主方法中執行以下操作：
kadane := getKadane(arr)，sum := getSum(arr)，prefix := getPrefix(arr)，suffix := getSuffix(arr)
如果 k 為 1，則返回 kadane
如果 sum > 1，則返回 (sum * (k - 2)) + prefix + suffix 和 kadane 的最大值
否則返回 (prefix + suffix) 和 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
255 次瀏覽
