LeetCode #53 Maximum Subarray Solution & Explanation

LeetCode Problem

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.

LeetCode #53 Examples and Constraints

Solution

Look at the problem, we can find the keyword -【contiguous 】, that means we will use iteration to solve the it.

C# Solution

First try – Time Limit Exceeded

public class Solution {
    public int MaxSubArray(int[] nums) {
        int max = (int)Math.Pow(10, 4)*-1 -1;
        
        for(int i = 0;i<nums.Length;i++)
        {
            int tmp = nums[i];
            if(tmp>max)
            {
                max = tmp;
            }
            for(int j = i+1;j<nums.Length;j++)
            {
                tmp+=nums[j];
                if(tmp>max)
                {
                    max = tmp;
                }
            }
        }
        
        return max;
    }
}

In this first try, we used a easy nested loop to find out the max value, but the poor time complexity makes it 【Time Limit Exceeded】.

Time Complexity : O(n2)

Solution1 – iteration

In this solution, if the sum of elements is greater than 0, we will keep the sum to the next iteration, or we will reset it to 0.

public class Solution {
    public int MaxSubArray(int[] nums) {
        int max = nums[0];
        int tmp =0;
        for(int i = 0;i<nums.Length;i++)
        {
            tmp+=nums[i];
            if(tmp>max)
            {
                max = tmp;
            }
            if(tmp<0)
            {
                tmp = 0;
            }
        }
        return max;
    }
}

Runtime : 270ms、206ms、249ms

Time Complexity : O(n)

Java Solution

Solution1

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int tmp =0;
        for(int i = 0;i<nums.length;i++)
        {
            tmp+=nums[i];
            if(tmp>max)
            {
                max = tmp;
            }
            if(tmp<0)
            {
                tmp = 0;
            }
        }
        return max;
    }
}

Runtime : 2ms、1ms、1ms Faster than 100% ( 1ms )

Time Complexity : O(n)

Python3 Solution

Solution1

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max = nums[0]
        tmp =0
        for i in range(0,len(nums)):
            tmp+=nums[i]
            
            if(tmp>max):
                max = tmp
            
            if(tmp<0):
            
                tmp = 0
            
        return max

Runtime : 692ms、674ms、897ms

Time Complexity : O(n)

JavaScript Solution

Solution1

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    var max = nums[0];
    var tmp =0;
    for(var i = 0;i<nums.length;i++)
    {
        tmp+=nums[i];
        if(tmp>max)
        {
            max = tmp;
        }
        if(tmp<0)
        {
            tmp = 0;
        }
    }
    return max;
};

Runtime : 90ms、75ms、98ms


Submission Detail


Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot

If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)

The problem link : Maximum Subarray – LeetCode

Latest Post

Leave a Reply

Your email address will not be published. Required fields are marked *