Mảng con lớn nhất có tổng lớn hơn k trong C ++

Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm mảng con lớn nhất có tổng lớn hơn k.

Hãy xem các bước để giải quyết vấn đề.

• Khởi tạo mảng.
• Lặp lại trên mảng và lưu trữ tổng tại mỗi chỉ mục trong một vectơ cùng với chỉ mục.
• Sắp xếp các tổng ở trên dựa trên tổng và chỉ số.
• Khởi tạo một mảng để lưu trữ các chỉ mục.
• Viết một vòng lặp lặp lại cho đến n.
  • Cập nhật các giá trị với chỉ số tối thiểu của mảng chỉ mục ở trên và chỉ số mảng tổng trước đó.
• Tổng khởi tạo bằng 0.
• Viết một vòng lặp lặp lại cho đến n.
  • Thêm phần tử hiện tại vào tổng.
  • Nếu tổng lớn hơn k.
    • Độ dài mảng con tối đa là i + 1.
  • Khác, độ dài mảng con tối đa là
    • Tìm chỉ mục từ các tổng trước đó bằng cách sử dụng tìm kiếm nhị phân.
    • Tổng nhỏ hơn sum - k - 1 là chỉ số phần tử chúng ta muốn.

Ví dụ

Hãy xem mã.

#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;
}

Đầu ra

Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.

6

Kết luận

Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.