Easy algorithm-Leet code- Maximum sub array

user_17264363 0
Viewed 510

Struggling to wrap my head around this.

Maximum Subarray Easy 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 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

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        subarray1=[]
        subarray2=[]
    
        for n in nums:
            subarray1.append(sum(nums[nums.index(n):]))
            nums2=nums[::-1]
            subarray2.append(sum(nums2[nums.index(n):]))
            para1=subarray1.index(max(subarray1))
            para2=len(nums)-subarray2.index(max(subarray2))
            ans=sum(nums[para1:para2])
        
        if sum(nums)>ans :
            ans=sum(nums)
        
        if len(nums)==2 and sum(nums)< nums[0] or nums[1] :
            ans=max(nums)
       
        return ans

I'm don't understand the iterative logic and the answers from vids are coming up wrong. My logic is to create an array summing the input array from both sides and use the index of max values on those 2 arrays to figure out the maximum sum sub array parameters.

My answer is supposedly wrong when copied onto leet code https://leetcode.com/problems/maximum-subarray/

Been trying for hours, it's marked as easy. Im sure there is an easy iterative way of doing it but everything I've search is wrong so far.

data-structures algorithm python
3 Answers

There is a standard logic to many of these problems. Assume you know what subarray with the largest total is nums[:n - 1]. Then what is the subarray with the largest total you can find for the subarray nums[:n]?

There are two possibilities:

  • The new answer doesn't contain nums[n-1]. In that case, it has to be the same answer as the old answer
  • The new answer does contain nums[n-1].

So. . . The actual algorithm is that you iteratively go through the array, repeatedly adding a new element to the array, and keeping track of two answers:

  1. What is the subarray with the largest total
  2. What is the subarray with the largest total containing the last element. (This answer may be the same as the previous.)

When you then add a new element to the end of the array:

  1. The subarray with the largest total is either (a) the previous largest total or (b) the previous largest total containing the last element plus the new last element or (c) just the last element. Pick the one with the largest total.
  2. The subarray with the largest total containing the last element is the larger of (b) or (c) above.
user_64574070 
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)

This is a 2 pass O(n) time complexity solution with constant space.

How it works: We add each element to its predecessor, provided the predecessor is greater than 0 (greater or equal would also do). The Idea is this: If negative numbers have managed to take it below 0, we discard the prefix and don't care about them anymore. But if some positive value is remaining, we add it since it's better than nothing.

At the end we look for the max value.

To make it one pass, you could just have a best value that at each iteration takes the max. Then you wouldn't need to loop over the array at the end again to take the max.

This is by the way Kadane's algorithm, if you are interested to further read about it.

user_77556650

Here's my solution, although it exceeds time limit when the input list has a lot of elements. My idea is to try the sum of every sublist and update the max sum accordingly. There's a faster, but more complex approach by using "divide and conquer" method: https://leetcode.com/problems/maximum-subarray/discuss/1849465/Divide-and-Conquer-Approach-with-Python

My solution (works in 200/209 cases because of Time Limit Exceeded):

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = - 10 ** 4

        for i in range(len(nums)):
            for j in range(i + 1, len(nums) + 1):
                s = sum(nums[i:j])
                if max_sum < s:
                    max_sum = s
        return max_sum
user_164737010
Related