微客导航 » 文章资讯 » C ++中最大总和大于k的最大子数组

C ++中最大总和大于k的最大子数组

2023-06-21 20:18:03 199

在本教程中，我们将编写一个程序，该程序查找最大子数组的总和大于k。

让我们看看解决问题的步骤。

初始化数组。

遍历数组，并将总和与索引一起存储在向量中的每个索引处。

根据总和和索引对上述总和排序。

初始化数组以存储索引。

编写一个循环直到n的循环。

用上述索引数组的最小索引和先前的总和数组索引更新值。

将总和初始化为0。

编写一个循环直到n的循环。

使用二进制搜索从先前的总和中找到索引。

小于sum-k-1的和是我们想要的元素索引。

最大子数组长度为i+1。

将当前元素相加。

如果总和大于k。

否则，最大子数组长度为

使用二进制搜索从以前的和中查找索引。

小于sum-k-1的和就是我们需要的元素索引。

示例

让我们看一下代码。

#include 
using namespace std;
bool compare(const pair& a, const pair& b) {
   if (a.first == b.first) {
      returna.second< b.second;
   }
   returna.first< b.first;
}
int findIndex(vector >& 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 > 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;
}

输出结果

如果运行上面的代码，则将得到以下结果。

返回顶部
3162201930
czq8825@qq.com

C ++中最大总和大于k的最大子数组

示例

热门推荐

随机推荐