Maximum SubArray

Problem Statement

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6

Link to GitHub: Code

Solution

• We need to have 2 variables one for storing max in the iteration and one for storing max so far
• Both variables would be initialized to the first element of the array
• Keep comparing the largest sum and and max till we reach end of the loop

package Algorithms.Arrays;

public class MaximumSubArray {
 public static int get(int arr [])
 {
  int maxsoFar=arr[0], maxEndingHere=arr[0];
  for (int i=1;i<arr.length;i++)
  {
   //Get the max in the iteration
   maxEndingHere=Math.max(maxEndingHere+arr[i], arr[i]);
   //Get the max so far
   maxsoFar=Math.max(maxEndingHere, maxsoFar);
  
  }
  return maxsoFar;
  
 }

}

Iteration