Maximum Subarray Problem

Maximum Subarray Problem:
The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Let us solve this problem step-by-step. The naive and simplest brute-force solution would be to consider each index of the array as the start of the subarray and checking if the sum till each of the further indices in the array is maximum. Assuming n to be the size of the array, we will iterate through the array n times to fix the start i of the subarray and for each of these n start indices, we will iterate n-i times through the array for finding the end index of the maximum sum subarray. Hence, the time complexity of the solution will be: O(n^2).

Algorithm: 

def max_subarray(A, n):

    left = right = 0

    max_sum = -INF

    for i = 0 to n:

        sum = 0

        for j = i to n:

            sum = sum + A[i]

            if sum > max_sum:

               max_sum = sum

               left = i

               right = j

    return (left, right, max_sum)

Code in C++:

Algorithm:

def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Code in C++:

 

Time Complexity: O(n)