LeetCode has an Easy coding Problem in Its’ Algorithm Section “Maximum Subarray LeetCode Python”. Today We are going to solve this problem in Python. LeetCode Link of the Problem is HERE

**Question**

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.

**Example**s

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

Input:nums = [1]Output:1

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

**Constraints:**

`1 <= nums.length <= 10`

^{5}`-10`

^{4}<= nums[i] <= 10^{4}

**Solution to Maximum Subarray LeetCode Python**

The basic idea behind Kadane’s approach is to search the array for all positive contiguous segments (max ending here is utilised for this). Also, among all positive segments, maintain track of the greatest total contiguous segment (max so far). We compare each positive sum to max so far and update max so far if it is more than max so far.

```
Lets take the example:
{-2, -3, 4, -1, -2, 1, 5, -3}
max_so_far = INT_MIN
max_ending_here = 0
for i=0, a[0] = -2
max_ending_here = max_ending_here + (-2)
Set max_ending_here = 0 because max_ending_here < 0
and set max_so_far = -2
for i=1, a[1] = -3
max_ending_here = max_ending_here + (-3)
Since max_ending_here = -3 and max_so_far = -2, max_so_far will remain -2
Set max_ending_here = 0 because max_ending_here < 0
for i=2, a[2] = 4
max_ending_here = max_ending_here + (4)
max_ending_here = 4
max_so_far is updated to 4 because max_ending_here greater
than max_so_far which was -2 till now
for i=3, a[3] = -1
max_ending_here = max_ending_here + (-1)
max_ending_here = 3
for i=4, a[4] = -2
max_ending_here = max_ending_here + (-2)
max_ending_here = 1
for i=5, a[5] = 1
max_ending_here = max_ending_here + (1)
max_ending_here = 2
for i=6, a[6] = 5
max_ending_here = max_ending_here + (5)
max_ending_here = 7
max_so_far is updated to 7 because max_ending_here is
greater than max_so_far
for i=7, a[7] = -3
max_ending_here = max_ending_here + (-3)
max_ending_here = 4
```

**Coding Solution**

```
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_so_far = -10000000
max_ending_here = 0
for i in range(0, len(nums)):
max_ending_here = max_ending_here + nums[i]
if (max_so_far < max_ending_here):
max_so_far = max_ending_here
if max_ending_here < 0:
max_ending_here = 0
return max_so_far
```

**Success:**

Runtime: 586 ms, faster than 92.30% of Python online submissions for Maximum Subarray.Memory Usage: 25.6 MB, less than 75.08% of Python online submissions for Maximum Subarray.

#### READ MORE

**Python-related** posts Visit **HERE**

**C++** related posts Visit **HERE**

**Databases** related posts Visit **HERE**

**Data Structures **related posts visit **HERE**

**Algorithms **related posts visit **HERE**

**Data Science** related posts visit **HERE**