Firstly let us understand what this question is exactly. Given a one-dimensional array of numbers, the objective is to find out the sub-array with the largest sum and print that sum. Let us break down the various concepts in the problem.

What is a Sub-Array

A subarray is commonly defined as a part or section of an array. For example, if we are given an array arr = [ 1, 2, 3 ] the sub-arrays are [1], [2], [3], [1,2], [2,3], [1,2,3] The formula to find the number of all the possible subarrays for a given array is subarray_count = N * ( N + 1 ) / 2 where N is the size of the array.

Naive Approach

The simplest brute force approach to solving this problem would be to use a nested for loop and find all possible sub-arrays for the given array.

Code

from sys import maxsize
arr = [1,2,3]
maxSum = -maxsize-1
for i in range(len(arr)):
    sum = 0
    for j in range(i,len(arr)):
        sum += arr[i]
        maxSum = max(maxSum,sum)
print(maxSum)

Output: 6

Time Complexity : 0(n^2)

Kadane's Algorithm

The basic idea behind Kadane's Algorithm is to look for all the positive contiguous sub-arrays and keep track of the maximum sum contiguous sub-array among all positive segments. There are two variables we will be keeping track of, maximum_sum and current_sum. While iterating over the array from start to end keep updating the current_sum value to the maximum of current_sum + element at the ith place and element at the ith place. Finally, update the maximum sum to the maximum value between maximum_sum and current_sum. Doing this will keep updating the value of maximum_sum to the largest possible value in a contiguous sub-array.

Code

from sys import maxsize
arr = [-1,2,3,5]

if(len(arr)==1):
        return arr[0]
maximum_sum = arr[0]
current_sum = -maxsize-1
for i in range(len(nums)):
        current_sum = max(current_sum+arr[i], arr[i])
        maximum_sum = max(maximum_sum,current_sum)
print(maximum_sum)

Output : 10

Time Complexity: O(n)

Space Complexity: O(1)

The solution takes O(n) time because we only iterate through the array once.

We are importing maxsize as it is the maximum value for an integer in python and to find the least value we use -maxsize - 1. To better understand the implementation of Kadane's Algorithm we will take a test case and dry run it on our code.

Consider a short example arr = [-1,2,3]

Initially value of current_sum = least value possible and maximum_sum = arr[0] which is -1

First Iteration:

current_sum = max(current_sum+(-1),-1). -1 is greater so update the value of current_sum to -1. maximum_sum = max(-1,-1) so there will be no change.

Second Iteration:

current_sum = max(-1+2,2). 2 is greater so update the value of current_sum to 2. maximum_sum = max(-1,2) so maximum_sum is updated to 2

Third Iteration:

current_sum = max(2+3,3). 5 is greater so update current_sum to 3. maximum_sum = max(2,5) so maximum_sum is updated to 5.

The loop ends and maximum_sum = 5 is printed.

Kadane's Algorithm is a very important algorithm while preparing for coding interviews and is one of the most sought-after questions during the interview coding round.