# 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…)