Cho mảng n số nguyên, tìm tổng lớn nhất của các mảng con tăng chặt. Ví dụ [1,2,3,2,5,1,7] → 8 (mảng con [1,7]).
Theo dõi tổng hiện tại và tổng max. Nếu arr[i] > arr[i-1] cộng vào tổng hiện tại, ngược lại cập nhật max và reset tổng hiện tại bằng arr[i].
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); }
Kết quả
Maximum sum : 8