数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告