Maximum Subarray LeetCode Python – Solution

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.

subarray is a contiguous part of an array.

Examples

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [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 <= 105
  • -104 <= nums[i] <= 104

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

Share the Knowledge