Find the subarray with least sum in the given array in O(N) time

Question

Example array : {0,1,1,1,-5,2,-4,89} .

Answer = -7 {-5,2,-4} is the subarray with least possible sum.

 

Rules :

1)Explanation of algorithm in your answer is a must .

2)Writing code is optional .

3)If code is written , make sure to you use format option from the editor .

Answer 1

#include <iostream>

using namespace std;

int minSubArraySum(int arr[], int n)

{ //arr -> integer array, n -> len(arr)

    int currMin, minimum;

    currMin = minimum = arr[0]; // initially current minimum and global minimum is the first element of array

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

    {

        // compare previous sum and present element and assign minimum value to currMin

        currMin = min(arr[i], arr[i] + currMin);

 

        // compare minimum and currMin assign min of minimum and mcurrMin to minimum

        minimum = min(minimum, currMin);

    }

    return minimum;

}