Tìm tổng tối đa tăng nghiêm ngặt mảng con trong C ++

Giả sử chúng ta có một mảng n số nguyên. Tìm tổng tối đa của các mảng con tăng dần. Vì vậy, nếu mảng giống như [1, 2, 3, 2, 5, 1, 7], tổng là 8. Trong mảng này có ba mảng con tăng dần, chúng là {1, 2, 3}, {2 , 5} và {1, 7}. Mảng con có tổng tối đa là {1, 7}

Để giải quyết vấn đề này, chúng ta phải theo dõi tổng tối đa và tổng hiện tại. Đối với mỗi phần tử arr [i] nếu giá trị này lớn hơn arr [i - 1] thì chúng ta cộng giá trị này vào tổng hiện tại, ngược lại arr [i] là điểm bắt đầu của một mảng con khác. Vì vậy, chúng tôi sẽ cập nhật tổng hiện tại dưới dạng mảng. Trước khi cập nhật tổng hiện tại, chúng tôi sẽ cập nhật tổng tối đa nếu được yêu cầu.

Ví dụ

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

Đầu ra

Maximum sum : 8