Largest sum contiguous subarray

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:

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 
Time complexity : O(N)
Java Program to find largest sum contiguous subarray:
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
When you run above program, you will get below output:
Largest sum continuous subarray is  9