## Wednesday, May 4, 2022

### Question 37 : Largest sum contiguous subarray.

Largest sum contiguous subarray is the task of finding the contiguous subarray within a one-dimensional array of numbers 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``

#### Solution 1:

Use two loops and try each combination of array elements to find maximum sum.
Time complexity : O(N^2)

#### Solution 2:

I have discussed Kadane ‘s algorithm in previous post. You can refer it.
Time complexity : O(N)

#### Solution 3:

Dynamic Programming:
You can use dynamic programming to solve this problem.
Lets say array be arr[] and maximum sum upto index i is maxSum(i)
Logic which can be used for dynamic programming:

``   maxSum(i) = Max of (maxSum(i-1) + a[i] , a[i])``

So it can be define as
Max sum at index i is maximum of (max sum upto i-1 + current element , current element)
Java code  :

``````public int dynamicProgramForMaxSubArray(int[] arr) {
int[] result = new int[arr.length];
result[0]=arr[0];
for (int i = 1; i < arr.length; i++) {
result[i]=Math.max(result[i-1]+arr[i], arr[i]);
}
int maxSumArray = result[0];
for (int j = 1; j <result.length ; j++) {
if(maxSumArray<result[j])
maxSumArray = result[j];
}

return maxSumArray;
}``````

Time complexity : O(N)

### Java Program to find largest sum contiguous subarray:

``````public class MaximumSubArrayMain {

/* Dynamic programming algorithm to find largest sum continuous subarray
*/
public int dynamicProgramForMaxSubArray(int[] arr) {
int[] result = new int[arr.length];
result[0]=arr[0];
for (int i = 1; i < arr.length; i++) {
result[i]=Math.max(result[i-1]+arr[i], arr[i]);
}
int maxSumArray = result[0];
for (int j = 1; j              if(maxSumArray<result[j])
maxSumArray = result[j];
}

return maxSumArray;
}
public static void main(String args[]) {
int arr[] = { 1, 8, -3, -7, 2, 7, -1, -9 };
MaximumSubArrayMain maxSum = new MaximumSubArrayMain();
System.out.println("Largest sum continuous subarray is " + maxSum.dynamicProgramForMaxSubArray(arr));
}
}``````

When you run above program, you will get below output:

``Largest sum continuous subarray is  9``

Don't miss the next article!
Be the first to be notified when a new article or Kubernetes experiment is published.