Find Maximum Sum Strictly Increasing Subarray - GeeksforGeeks

Find Maximum Sum Strictly Increasing Subarray - GeeksforGeeks

Given an array of positive integers. Find the maximum sum of strictly increasing subarrays. Note that this problem is different from maximum subarray sum and maximum sum increasing subsequence problems.

An efficient solution of this problem take O(n) time. The idea is keep track of maximum sum and current sum. For every element arr[i], if it is greater than arr[i-1], then we add it to current sum. Else arr[i] is starting point of another potential candidate for maximum sum increasing subarray, so we update current sum as array. But before updating current sum, we update maximum sum if required.

int maxsum_SIS(int arr[] , int n)

{

    // Initialize max_sum be 0

    int max_sum = 0;

 

    // Initialize current sum be arr[0]

    int current_sum = arr[0] ;

 

    // Traverse array elements after first element.

    for (int i=1; i<n ; i++ )

    {

        // update current_sum for strictly increasing subarray

        if (arr[i-1] < arr[i])

            current_sum = current_sum + arr[i];

 

        else // strictly increasing subarray break

        {

            // update max_sum and current_sum ;

            max_sum = max(max_sum, current_sum);

            current_sum = arr[i];

        }

    }

 

    return max(max_sum, current_sum);

}

Read full article from Find Maximum Sum Strictly Increasing Subarray - GeeksforGeeks