package com.fishercoder.solutions;

/**
 * 53. Maximum Subarray
 *
 * 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.
 */

public class _53 {

  public static class Solution1 {
    /**credit: https://discuss.leetcode.com/topic/5000/accepted-o-n-solution-in-java*/
    public int maxSubArray(int[] nums) {
      int maxSoFar = nums[0];
      int maxEndingHere = nums[0];
      for (int i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxEndingHere, maxSoFar);
      }
      return maxSoFar;
    }
  }
}

@@ -59,21 +59,47 @@
 array%0A *
-%0A * F
+ Given an integer array nums, f
 ind the 
@@ -122,24 +122,8 @@
 ray 
-within an array 
 (con
@@ -180,125 +180,294 @@
  sum
-.%0A * For example, given the array %5B-2,1,-3,4,-1,2,1,-5,4%5D, the contiguous subarray %5B4,-1,2,1%5D has the largest sum = 6
+ and return its sum.%0A *%0A * Example:%0A * Input: %5B-2,1,-3,4,-1,2,1,-5,4%5D,%0A * Output: 6%0A * Explanation: %5B4,-1,2,1%5D has the largest sum = 6.%0A *%0A * Follow up:%0A * If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle
 .%0A *

refactor 53