Largest Sum Contiguous Subarray
A Subarray is an array that is the contiguous part of an array. Consider the given array nums; we have to find the contiguous array containing positive and negative numbers, returns its sum.
Suppose the array is:
A: [-2, 1, -3, -1, 2, 1, -5, 4]
We can observe in the above array that the array contains both negative and positive integers. The indices in the above array start from 0 to 8. Now the question is, “What contiguous array has the largest sum”. What does contiguous mean? Here contiguous means that we do not have a break in a snippet that we take from the array. In the above example, -2 and 1 is a contiguous array, -3, and -1 is a contiguous array, 2 and 1 is a contiguous array. If we consider the elements {-2, 1, -1, 2} is a non-contiguous array because we have a break here.
Here, we require a contiguous sub-array with the largest sum. The solution to this problem is that first, we find all the possible sub-arrays and then find the sub-array with the largest sum value. This leads to a quadratic time or cubic time.
Consider the array which is given below:
B: {-5, 4, 6, -3, 4, 1}
There are multiple techniques to solve this problem. First, we look at brute force to solve the problem. In the case of brute force, first, we have to find all the sub-arrays, and then we look at the sub-array, which has the maximum sum.
The below algorithm is used to implement the brute force:
The above algorithm has the time complexity of O(n2). The time complexity is high, so we need to optimize the problem. In order to optimize the problem, we use Kaden’s algorithm.
What is Kaden’s algorithm?
Kaden’s algorithm is an iterative dynamic programming algorithm that looks for the maximum contiguous subarray. Using the Kaden’s algorithm, we should consider only the positive elements of the array and keep track of only the maximum contiguous sum subarray.
Kaden’s Algorithm
Let’s dry run the code.
If the array is A: {5, -4, -2, 6, -1}
When i=0;
A[0] = 5
current_sum = current_sum + A[0]
= 0+5 = 5
Since current_sum > maximum_sum, i.e., 5 > 0, so
maximum_sum = 5
When i = 1;
A[1] = -4
current_sum = current_sum + A[1]
= 5 – 4 = 1
Since current_sum < maximum_sum, so maximum_sum!= current_sum
When i = 2;
A[2] = -2
current_sum = current_sum + A[2]
= 1 – 2 = -1
Since current_sum < maximum_sum, so maximum_sum is not equal to current_sum. The value of current_sum is negative, so current_sum is equal to 0.
When i = 3;
A[3] = 6
current_sum = current_sum + A[3]
= 0 + 6 = 6
In this case, current_sum is greater than maximum_sum, i.e., (6>5), so maximum_sum is equal to current_sum, i.e., 6.
When i = 4;
A[4] = -1
current_sum = current_sum + A[4]
= 6 – 1 = 5
Since current_sum<maximum_sum, so maximum_sum is not equal to current_sum.
Therefore, the maximum_sum of the contiguous array is 6.
Implementation in C
// Program to implement the largest sum contiguous array
Output
