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

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.