×

Welcome to TagMyCode

Please login or create account to add a snippet.
0
0
 
0
Language: Python
Posted by: ls sean
Added: Sep 15, 2021 4:02 PM
Modified: Sep 15, 2021 4:02 PM
Views: 3041
  1. '''
  2. https://leetcode.com/problems/maximum-subarray/
  3. '''
  4. from sorting.sorting_util import SortingUtil
  5. import snoop
  6.  
  7. class Solution:
  8.     @snoop
  9.     '''
  10.    https://leetcode.com/submissions/detail/554962768/
  11.    '''
  12.     def maxSubArray(self, nums):
  13.         s = nums[0]
  14.         best = nums[0]
  15.         for i in range(1,len(nums)):
  16.             s = max(nums[i], s + nums[i])
  17.             best = max(best,s)
  18.         return best
  19.  
  20.     def maxSubArray(self, nums):
  21.         '''
  22.        https://leetcode.com/submissions/detail/554970285/
  23.        '''
  24.         if len(nums) == 1:
  25.             return nums[0]
  26.  
  27.         prefix_sum = nums[0]
  28.         largest = nums[0]
  29.         for num in nums[1:]:
  30.             if prefix_sum < num and prefix_sum < 0:
  31.                           #when negative
  32.                           #we do not need to include all previous numbers if the sum is smaller than next number
  33.                 prefix_sum = num
  34.             else:
  35.                 prefix_sum += num
  36.  
  37.             if prefix_sum > largest:
  38.                 largest = prefix_sum
  39.  
  40.         return largest
  41. if __name__ == '__main__':
  42.     #arr = SortingUtil.generate_random_array(5)
  43.     arr = [2,6,4,8,10,9,15]
  44.     #arr = [1]
  45.     #arr = [-1]
  46.     #print(Solution().productExceptSelf(arr))
  47.     print(Solution().maxSubArray(arr))
  48.