CODEWITHSUNDEEP
pythonpython-3.x
user10062624
user10062624

Reputation:

What's wrong for the error of Time Limit Exceeded on leetcode 53. Maximum Subarray?

My code is below for leetcode 53.Maximum Subarray, but one test case is not passed.

How can I fix my current code to prevent Time Limit Exceeded?

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = nums[0]
        array_len = len(nums)
        for i in range(array_len):
            #print("first index" + str(i))
            total = 0
            for j in range(i, array_len):

                total = total + nums[j]
                #print(total)

                if result < total:
                    result = total

        return result

Upvotes: 0

Views: 387

Answers (2)

TimeGo
TimeGo

Reputation: 26

I think you can use some algorihm function to reduce your time complexity;lick max() in c++. You can use iteration to solut it.

Upvotes: 1

Md Golam Rahman Tushar
Md Golam Rahman Tushar

Reputation: 2375

You are getting TLE because your solution's runtime is O(n^2). The time complexity can be reduced by two ways. Either you need to use divide and conquer approach which has O(nlogn) runtime or Kadane`s algorithm which has O(n) runtime. Either of the approaches will be enough.

Upvotes: 0

Related Questions