Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

&nbsp;
Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.


Example 2:

Input: nums = [1]
Output: 1


Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	-104 &lt;= nums[i] &lt;= 104


&nbsp;
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.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def kadane(i):
            if F[i] != None:
                return F[i]
            F[i] = max(nums[i],kadane(i-1) + nums[i])
            return F[i]
        n = len(nums)
        F = [None for _ in range(n)]
        F[0] = nums[0]
        kadane(n-1)
        return max(F)
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int currmax = 0;
        int gmax = nums[0];
        for(int i=0;i<n;i++) {
            currmax+=nums[i];
            gmax=Math.max(gmax, currmax);
            currmax=Math.max(currmax, 0);
        }
        return gmax;
    }
}
class Solution {
public:
    int maxSubArray(vector<int>& nums)
    {
        int m = INT_MIN, sm = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            sm += nums[i];
            m = max(sm, m);
            if (sm < 0) sm = 0;
        }
        return m;
    }
};
/**
 * @param {number[]} nums
 * @return {number}
 */
 var maxSubArray = function(nums) {
   let max = Number.MIN_SAFE_INTEGER;
   let curr = 0;
   for (let i = 0; i < nums.length; i++) {
      if (curr < 0 && nums[i] > curr) {
          curr = 0;
      }
    curr += nums[i];
    max = Math.max(max, curr);
   }
  return max;
}; 
Maximum Subarray