資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中求和大於 k 的最大子陣列
在本教程中，我們將編寫一個程式，查詢和大於 k 的最大子陣列。
讓我們看看解決問題的步驟。
- 初始化陣列。
- 遍歷陣列，並將每個索引處的和儲存在一個向量中，同時儲存索引。
- 根據和和索引對上述和進行排序。
- 初始化一個數組來儲存索引。
- 編寫一個迴圈，迭代到 n。
- 使用上述索引陣列的最小索引和前一個和陣列的索引更新值。
- 將和初始化為 0。
- 編寫一個迴圈，迭代到 n。
- 將當前元素新增到和中。
- 如果和大於 k。
- 最大子陣列長度為 i + 1。
- 否則最大子陣列長度為
- 使用二分查詢從之前的和中查詢索引。
- 小於 sum - k - 1 的和是我們要查詢的元素索引。
示例
讓我們看看程式碼。
#include <bits/stdc++.h>
using namespace std;
bool compare(const pair<int, int>& a, const pair<int, int>& b) {
if (a.first == b.first) {
return a.second < b.second;
}
return a.first < b.first;
}
int findIndex(vector<pair<int, int> >& previousSums, int n, int val) {
int start = 0;
int end = n - 1;
int mid, result = -1;
while (start <= end) {
mid = (start + end) / 2;
if (previousSums[mid].first <= val) {
result = mid;
start = mid + 1;
}else {
end = mid - 1;
}
}
return result;
}
int getLargestSubArray(int arr[], int n, int k) {
int maxLength = 0;
vector<pair<int, int> > previousSums;
int sum = 0, minIndexes[n];
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
previousSums.push_back({ sum, i });
}
sort(previousSums.begin(), previousSums.end(), compare);
minIndexes[0] = previousSums[0].second;
for (int i = 1; i < n; i++) {
minIndexes[i] = min(minIndexes[i - 1], previousSums[i].second);
}
sum = 0;
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
if (sum > k) {
maxLength = i + 1;
}else {
int ind = findIndex(previousSums, n, sum - k - 1);
if (ind != -1 && minIndexes[ind] < i) {
maxLength = max(maxLength, i - minIndexes[ind]);
}
}
}
return maxLength;
}
int main() {
int arr[] = { 5, 3, -3, 2, 4, 7 };
int k = 5, n = 6;
cout << getLargestSubArray(arr, n, k) << endl;
return 0;
}輸出
如果執行上述程式碼，則將獲得以下結果。
6
結論
如果您在本教程中有任何疑問，請在評論部分提出。
更新於: 2021年4月9日
292 次瀏覽
廣告