資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的最大圓形子陣列
假設我們有一個由 A 表示的整數迴圈陣列 C，我們需要找到 C 的非空子陣列的最大可能和。此外，子陣列只能包含固定緩衝區 A 中的每個元素最多一次。如果陣列類似於 [1,-2,3,-2]，則輸出將為 3。這是因為子陣列 [3] 的最大和為 3。
為了解決這個問題，我們將遵循以下步驟：
n := v 的大小
建立大小為 n 的陣列 leftSum、leftSumMax、rightSum、rightSumMax
leftSum[0] := v[0]，leftSumMax[0] := 0 和 v[0] 中的最大值
對於 i 從 1 到 n – 1
leftSum[i] := leftSum[i - 1] + v[i]
leftSumMax[i] := leftSum[i] 和 leftSumMax[i - 1] 中的最大值
rightSum[n - 1] := v[n - 1]，leftSumMax[n - 1] := 0 和 v[n - 1] 中的最大值
對於 i 從 n - 2 到 0
rightSum[i] := rightSum [i + 1] + v[i]
rightSumMax[i] := rightSum[i + 1] 和 rightSum Max[i] 中的最大值
leftAns := leftSum[0] + rightSumMax[1]
對於 i 從 1 到 n – 2
leftAns := leftAns、leftSum[i] + rightSumMax[i + 1] 中的最大值
rightAns := rightSum[n - 1] + leftSumMax[n - 2]
對於 i 從 n - 2 到 1
rightAns := rightAns、rightSum[i] + leftSumMax[i - 1] 中的最大值
curr := v[0]，kadane := v[0]
對於 i 從 1 到 n – 1
curr := v[1]、curr + v[i] 中的最大值
kadane := curr 和 kadane 中的最大值
返回 leftAns、rightAns 和 kadane 中的最大值
讓我們看一下以下實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSubarraySumCircular(vector<int>& v) {
int n = v.size();
vector <int> leftSum(n),leftSumMax(n),rightSum(n), rightSumMax(n);
leftSum[0] = v[0];
leftSumMax[0] = max((int)0,v[0]);
for(int i =1;i<n;i++){
leftSum[i] = leftSum[i-1] + v[i];
leftSumMax[i] = max(leftSum[i],leftSumMax[i-1]);
}
rightSum[n-1] = v[n-1];
rightSumMax[n-1] = max((int)0,v[n-1]);
for(int i =n-2;i>=0;i--){
rightSum[i] = rightSum[i+1]+v[i];
rightSumMax[i] = max(rightSumMax[i+1],rightSum[i]);
}
int leftAns=leftSum[0]+rightSumMax[1];
for(int i =1;i<n-1;i++){
leftAns = max(leftAns,leftSum[i]+rightSumMax[i+1]);
}
int rightAns = rightSum[n-1]+leftSumMax[n-2];
for(int i =n-2;i>=1;i--){
rightAns = max(rightAns,rightSum[i]+leftSumMax[i-1]);
}
int curr=v[0];
int kadane = v[0];
for(int i =1;i<n;i++){
curr = max(v[i],curr+v[i]);
kadane = max(curr,kadane);
}
return max(leftAns,max(rightAns,kadane));
}
};
main(){
vector<int> v = {1,-2,3,-2};
Solution ob;
cout << (ob.maxSubarraySumCircular(v));
}輸入
[1,-2,3,-2]
輸出
3
145 次檢視
