資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學C++ 中三個不重疊子陣列的最大和
假設我們有一個名為 nums 的正整數陣列，我們需要找到三個不重疊的子陣列，使得它們的和最大。這裡每個子陣列的大小都為 k，我們希望最大化所有 3*k 個元素的總和。
我們需要將結果表示為一個列表，其中包含每個區間的起始位置索引。如果有多個答案，我們將返回字典序最小的那個。
因此，如果輸入類似於 [1,2,1,2,6,8,4,1] 且 k = 2，則結果將為 [0,3,5]，因此子陣列 [1,2]、[2,6]、[8,4] 對應於起始索引 [0,3,5]。
為了解決這個問題，我們將遵循以下步驟：
- n := nums 的大小
- 定義一個大小為 3 的陣列 ret，並將其填充為無窮大
- 定義一個大小為 n + 1 的陣列 sum
- 對於初始化 i := 0，當 i < n 時，更新（i 增加 1），執行：
- sum[i + 1] = sum[i] + nums[i]
- 定義一個大小為 n 的陣列 posLeft
- 定義一個大小為 n 的陣列 posRight，並將其填充為 n - k
- 對於初始化 i := k，currMax := sum[k] - sum[0]，當 i < n 時，更新（i 增加 1），執行：
- newTotal := sum[i + 1] - sum[i + 1 - k]
- 如果 newTotal > currMax，則：
- currMax := newTotal
- posLeft[i] := i + 1 - k
- 否則
- posLeft[i] := posLeft[i - 1]
- 對於初始化 i := n - k - 1，currMax := sum[n] - sum[n - k]，當 i >= 0 時，更新（i 減少 1），執行：
- newTotal := sum[i + k] - sum[i]
- 如果 newTotal >= currMax，則：
- currMax := newTotal
- posRight[i] := i
- 否則
- posRight[i] := posRight[i + 1]
- req := 0
- 對於初始化 i := k，當 i <= n - 2 * k 時，更新（i 增加 1），執行：
- l := posLeft[i - 1], r := posRight[i + k]
- temp := (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r])
- 如果 temp > req，則：
- ret[0] := l, ret[1] := i, ret[2] := r
- req := temp
- 返回 ret
讓我們看看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
int n = nums.size();
vector <int> ret(3, INT_MAX);
vector <int> sum(n + 1);
for(int i = 0; i < n; i++){
sum[i + 1] = sum[i] + nums[i];
}
vector <int> posLeft(n);
vector <int> posRight(n, n - k);
for(int i = k, currMax = sum[k] - sum[0]; i < n; i++){
int newTotal = sum[i + 1] - sum[i + 1- k];
if(newTotal > currMax){
currMax = newTotal;
posLeft[i] = i + 1 - k;
}else{
posLeft[i] = posLeft[i - 1];
}
}
for(int i = n - k - 1, currMax = sum[n] - sum[n - k]; i >=0 ; i--){
int newTotal = sum[i + k] - sum[i];
if(newTotal >= currMax){
currMax = newTotal;
posRight[i] = i;
}else{
posRight[i] = posRight[i + 1];
}
}
int req = 0;
for(int i = k; i <= n - 2 * k; i++){
int l = posLeft[i - 1];
int r = posRight[i + k];
int temp = (sum[l + k] - sum[l]) + (sum[i + k] - sum[i]) + (sum[r + k] - sum[r]);
if(temp > req){
ret[0] = l;
ret[1] = i;
ret[2] = r;
req = temp;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1,2,6,8,4,1};
print_vector(ob.maxSumOfThreeSubarrays(v, 2));
}輸入
{1,2,1,2,6,8,4,1}
2輸出
[0, 3, 5, ]
更新於: 2020年6月2日
125 次檢視
廣告