C++で厳密に増加するサブアレイの最大合計を見つける

n個の整数の配列があるとします。厳密に増加するサブ配列の最大合計を求めます。したがって、配列が[1、2、3、2、5、1、7]のような場合、合計は8になります。この配列には、厳密に増加する3つのサブ配列があります。これらは{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