Table of Contents
If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.
Problem:
From Wikipedia :
In computer science, the 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 :
There are multiple solution to solve this problem:
Solution 1:
Use two loops and try each combination of array elements to find maximum sum.
Time complexity : O(N^2)
Solution 2:
Kadane ‘s algoritm
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:
|
1 2 3 |
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  :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
package org.arpit.java2blog; 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)); } } |
|
1 2 3 |
Largest sum continuous subarray is 9 |
