C++에서 엄격하게 증가하는 하위 배열의 최대 합 찾기

n개의 정수 배열이 있다고 가정합니다. 엄격하게 증가하는 부분배열의 최대 합을 찾습니다. 따라서 배열이 [1, 2, 3, 2, 5, 1, 7]과 같으면 합계는 8입니다. 이 배열에는 엄격하게 증가하는 세 개의 하위 배열이 있습니다. {1, 2, 3}, {2 , 5} 및 {1, 7}. 최대 합계 하위 배열은 {1, 7}입니다.

이 문제를 해결하려면 최대 합계와 현재 합계를 추적해야 합니다. 각 요소 arr[i]에 대해 이것이 arr[i – 1]보다 크면 이를 현재 합계에 추가하고, 그렇지 않으면 arr[i]는 다른 하위 배열의 시작점입니다. 따라서 현재 합계를 배열로 업데이트합니다. 현재 합계를 업데이트하기 전에 필요한 경우 최대 합계를 업데이트합니다.

예시

#include<iostream>
using namespace std;
int maximum(int a, int b){
   return (a>b)?a:b;
}
int maximum_sum_incr_subarr(int array[] , int n) {
   int max_sum = 0;
   int current_sum = array[0] ;
   for (int i=1; i<n ; i++ ) {
      if (array[i-1] < array[i])
         current_sum = current_sum + array[i];
      else {
         max_sum = maximum(max_sum, current_sum);
         current_sum = array[i];
      }
   }
   return max(max_sum, current_sum);
}
int main() {
   int arr[] = {1, 2, 3, 2, 5, 1, 7};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Maximum sum : " << maximum_sum_incr_subarr(arr , n);
}

출력

Maximum sum : 8