**Problem statement** – Given an array, find a contiguous sub-array whose sum is maximum. More precisely, if we have an array *A[0, 1, 2 … N]*, we need to find a sub-array *A[i, i + 1, i + 2, … j]* such that the sum of elements in the sub-array is maximum.

**Clues** –

- Your solution should be O(N) in time and O(1) in space.
- Can you think of a solution which solves the problem in a single scan of the array?

**Solution** – This is a popular interview question asked by the interviewers to test the basics of the candidate. This problem can be solved in O(N) time by using Kadane’s Algorithm. In this algorithm, we keep adding elements to a *sum* variable as we are traversing the array. This sum variable holds the sum of a sub-array. When the *sum* variable becomes negative, we cast off the the sub-array seen so far and reset *sum* variable. The final answer will be the maximum of all the values which were stored in *sum* over all iterations.

Example – For the array A = [-2 , 1, -3, 4, -1, 2, 1, -5, 4]

A[i] | Sub-array | sum |
Max sub-array | maxSum |

-2 | [-2] | 0 | [-2] | -2 |

1 | [1] | 1 | [1] | 1 |

-3 | [-3] | 0 | [1] | 1 |

4 | [4] | 4 | [4] | 4 |

-1 | [4, -1] | 3 | [4] | 4 |

2 | [4, -1, 2] | 5 | [4, -1, 2] | 5 |

1 | [4, -1, 2, 1] | 6 | [4, -1, 2, 1] | 6 |

-5 | [-5] | 3 | [4, -1, 2, 1] | 6 |

4 | [-5, 4] | 3 | [4, -1, 2, 1] | 6 |

**Code** –

public class Solution { public int maxSubArray(List<Integer> a) { int sum = 0; int maxSum = Integer.MIN_VALUE; for (int i = 0; i < a.size(); ++i) { if (sum + a.get(i) < 0) { // Adding this element will make the current // subarray sum negative, so don't add this element // and start a new subarray with next element sum = 0; } else { // Adding this element will increase the // current subarray sum, so add this // element to the current subarray sum += a.get(i); } // maxSum is the maximum of - // // 1. maxSum so far // 2. if sum == 0, then a.get(i) which is proably a -ve number // 3. if sum != 0, then sum of subarray so far maxSum = Math.max(maxSum, sum == 0 ? a.get(i) : sum); } return maxSum; } }

If you didn’t understand why we need the “*sum == 0 ? a.get(i) : sum*” condition in the end, think of the case where array A = [-3, -2, -1]. Basically when the array has all negative values, you’d want to return the largest among the negative values. Now remember, *sum* variable doesn’t store negative values, so when it holds 0, we consider *A[i]* instead of *sum*. Give it a little thought, I’m sure you’ll understand it. If you need a more explanation, refer to my post on Kadane’s Algorithm.