Kadane’s Algorithm: Largest sum increasing contiguous subarray

Coding Interview Questions

1 min read

Problem Statement:

You are given a positive integer array.

You need to find the largest sum of continuous increasing

Example:

Input: arr[] = [2, 1, 4, 5, 3]

Output = 10

Explanation: [1, 4, 5] is the continuous increasing subarray

Solution Explanation:

Iterate the array from 1 to end of the array.

If the element is greater than the previous element, then add the element,

else, update the max, and reset the sum value to the current element.

Then return the max element

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int solution(vector<int> arr) 
{
    int maxi = 0;
    int sum = arr[0];
    for(int i = 1; i < arr.size() ; i++)
    {
        if(arr[i] > arr[i-1])
        {
            sum += arr[i];
        }
        else
        {
            maxi = max(sum,maxi);
            sum = arr[i];
        }
    }
    return max(sum,maxi);
}

int main()
{
    vector<int> arr =  {2, 1, 4, 5, 3};
  
    cout << solution(arr);
    return 0;
}