# Find a sub-array with the largest sum

This problem is also known with the name: **Maximum sum sub array problem/Largest sum contiguous sub array problem.**

**Problem:** Given a one dimensional Array (containing both positive and negative numbers), write an efficient program to find a contiguous sub array in it which has a maximum sum.

**Problem Explanation:** You are given an array **a** = {1,3, -2, 8, -4, 0} So, all possible contiguous sub arrays present in **a **are:

{1}, {1,3}, {1,3,-2}, {1,3,-2,8}, {1,3,-2,8,-4}, {1,3,-2,8,-4,0}, {3}, {3,-2}, {3,-2,8}, {3,-2,8,-4}, {3,-2,8,-4,0}, {-2}, {-2,8}, {-2,8,-4}, {-2,8,-4,0}, {8}, {8,-4},

{8,-4,0}, {-4}, {-4,0}, {0}

now, find sum of each sub array found above and the answer would be the sub array which has the maximum sum among all…so, answer is: {1,3,-2,8,} with sum = 1+3+ (-2) + 8 = 10

**Method 1: Below program is based on an algorithm/approach given by Kadane and popularly known as Kadane’s algorithm**

public class MaxSumSubArray { // function to find maximum sum public static void maxSumSubArray(int[] a) { int maxSumFound = 0; int tempMaxSumFound = 0; int startIndex = 0; int endIndex = 0; for (int i = 0; i < a.length; i++) { tempMaxSumFound += a[i]; if (tempMaxSumFound < 0) { tempMaxSumFound = 0; startIndex = i+1; } else if (maxSumFound < tempMaxSumFound) { maxSumFound = tempMaxSumFound; endIndex = i; } } System.out.println("Maximum Contingous sum found is: "+ maxSumFound); System.out.println("has startIndex: "+startIndex); System.out.println("has endIndex: "+endIndex); } // test function public static void main(String[] args) { //int[] a = { 1, 2, 3, -2, 0 }; int[] a = { -1, -2, -3, -2}; maxSumSubArray(a); } }

Time Complexity: **O(n) **

*Solution Analysis: Method 1 is a good solution yet it misses one important case when all elements in the array are negative e.g {-1,-2} Method 2 below takes care of this case as well which has the same time complexity as Method 1 i.e O(n).*

**Method 2: The solution is almost same as Method 1 with a slight modification so as to handle the case when all elements in an array are negative.**

public class MaxSumSubArray { // function to find maximum sum public static void maxSumSubArray(int[] a) { int maxSumFound = a[0]; int tempMaxSumFound = a[0]; int tempStartIndex = 0; int startIndex = 0; int endIndex = 0; for (int i = 1; i < a.length; i++) { if (a[i] < tempMaxSumFound + a[i]) { tempMaxSumFound = tempMaxSumFound + a[i]; } else { tempMaxSumFound = a[i]; tempStartIndex = i; } if (maxSumFound < tempMaxSumFound) { maxSumFound = tempMaxSumFound; startIndex = tempStartIndex; endIndex = i; } } System.out.println("Maximum Contingous sum found is: " + maxSumFound); System.out.println("has startIndex: " + startIndex); System.out.println("has endIndex: " + endIndex); } // test function public static void main(String[] args) { //int[] a = { 1, 2, 3, -2, 0 }; int[] a = { -1, -2, -3, -2}; maxSumSubArray(a); } }

Time Complexity: **O(n) **

*Solution Analysis: Method 2 is one of the best solutions to approach to this problem and works absolutely fine for an array containing all negative elements, all positive elements and a mix of positive and a negative elements.*

Note: If you find any other better way to approach to this problem or you find any issue/error in above code snippets/approaches – please share it in the comments section below and get a chance to enrol free of cost for an online Live Data Structure and Algorithm course (specially designed for interview preparation for software companies like Amazon, Google, Facebook, FlipKart, SnapDeal, HealthKart…)