Given an array A of N integers, the task is to find the contiguous sub-array(containing at least one number) which has the maximum sum and return the sub-array and its sum.
Example 1: Find largest sum contiguous sub-array in: {-2, -3, 4, -1, -2, 1, 5, -3}
Input: {-2, -3, 4, -1, -2, 1, 5, -3}
Output:Sub-array: { 4 -1 -2 1 5 }, Sum: 7
Example 2: Find largest sum contiguous sub-array in: {1}
Input: {1}
Output:Sub-array: { 1 }, Sum: 1
Solutions
Method 1: Kadane's Algorithm (Print Sub-array)
We can solve this problem with Kadane's Algorithm, the algorithm requires at least one positive number, so all negative array is invalid input.
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).
Method 2: Kadane's Algorithm (Print Sub-array - all Negative Input)
This is a modified form of the original Kadane's Algorithm and also works for all negative array input.
There are three changes -
1) Initialize variables with the 0th element and start the loop from the 1st element.
2) While calculating "maxEndingHere", compare it with the current element ar[i] instead of "0" and assign maxEndingHere=ar[i] instead of maxEndingHere=0.
3) When "maxEndingHere < arr[i]" assign "i" instead of "i+1" to variable "newStart".
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).
Method 3: Kadane's Algorithm (Original)
We can solve this problem with Kadane's Algorithm, the algorithm requires at least one positive number, so all negative array is invalid input.
def max_subarray(numbers):
best_sum = 0
current_sum = 0
for x in numbers:
current_sum = max(0, current_sum + x)
best_sum = max(best_sum, current_sum)
return best_sum
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).
Method 4: Kadane's Algorithm (All Negative Input)
This version of Kadane's Algorithm also works with all negative elements array as input.
Complexity
The time complexity of this solution is O(n) and space complexity is O(1).