package com.fishercoder.solutions;

/**
 * 53. Maximum Subarray
 * Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
 *
 * Example:
 * Input: [-2,1,-3,4,-1,2,1,-5,4],
 * Output: 6
 * Explanation: [4,-1,2,1] has the largest sum = 6.
 *
 * Follow up:
 * If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
 */

public class _53 {

    public static class Solution1 {
      /**
       * https://leetcode.com/problems/maximum-subarray/discuss/20211/accepted-on-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;
      }
    }
}

@@ -33,448 +33,8 @@
 s;%0A%0A
-/**%0A * 53. Maximum Subarray%0A * Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum 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 */%0A%0A
 publ
@@ -95,12 +95,16 @@
     
+  
 /**%0A
+  
     
@@ -209,11 +209,15 @@
     
+ 
+ 
 */%0A
+  
     
@@ -251,24 +251,28 @@
 t%5B%5D nums) %7B%0A
+    
         int 
@@ -295,24 +295,28 @@
 0%5D;%0A        
+    
 int maxEndin
@@ -324,32 +324,36 @@
 Here = nums%5B0%5D;%0A
+    
         for (int
@@ -394,16 +394,22 @@
         
+      
 maxEndin
@@ -470,16 +470,22 @@
         
+ 
+     
 maxSoFar
@@ -526,26 +526,34 @@
 r);%0A        
-%7D%0A
+    %7D%0A    
         retu
@@ -565,16 +565,18 @@
 xSoFar;%0A
+  
       %7D%0A

refactor 53