10 examples of 'find largest sum contiguous subarray' in Python

Every line of 'find largest sum contiguous subarray' code snippets is scanned for vulnerabilities by our powerful machine learning engine that combs millions of open source libraries, ensuring your Python code is secure.

All examples are scanned by Snyk Code

By copying the Snyk Code Snippets you agree to
this disclaimer
9def maxSubArray(self, nums):
10 """
11 :type nums: List[int]
12 :rtype: int
13 """
14 if not nums:
15 return 0
16 length = len(nums)
17 current = nums[0]
18 m = current
19 for i in range(1, length):
20 if current < 0:
21 current = 0
22 current += nums[i]
23 m = max(current, m)
24 return m
Important

Use secure code every time

Secure your code as it's written. Use Snyk Code to scan source code in minutes – no build needed – and fix issues immediately. Enable Snyk Code

22def maxTwoSubArrays(self, nums):
23 """
24 dp max subarray
25
26 fi for subarry that ends WITH OR BEFORE i
27
28 f1 for forward sweeping
29 f2 for backward sweeping
30 :param nums: A list of integers
31 :return: An integer denotes the sum of max two non-overlapping subarrays
32 """
33 n = len(nums)
34
35 f = [[-1<<31 for _ in xrange(n+1)] for _ in xrange(2)]
36
37 cur = 0
38 for i in xrange(1, n+1):
39 cur += nums[i-1]
40 f[0][i] = max(nums[i-1], f[0][i-1], cur)
41 if cur < 0:
42 cur = 0
43
44 cur = 0
45 for i in xrange(n-1, -1, -1):
46 cur += nums[i]
47 f[1][i] = max(nums[i], f[1][i+1], cur)
48 if cur < 0:
49 cur = 0
50
51 maxa = -1<<31
52 for i in xrange(1, n):
53 maxa = max(maxa, f[0][i]+f[1][i])
54 return maxa
4def find_max_subarray(numbers):
5 max_till_here = [0]*len(numbers)
6 max_value = 0
7 for i in range(len(numbers)):
8 max_till_here[i] = max(numbers[i], max_till_here[i-1] + numbers[i])
9 max_value = max(max_value, max_till_here[i])
10 return max_value
2def minSubArrayLen(self, s, nums):
3 """
4 :type s: int
5 :type nums: List[int]
6 :rtype: int
7 """
8 # sliding window
9 left = 0
10 _min = sys.maxint
11 _sum = 0
12 for i in range(len(nums)):
13 _sum = _sum+nums[i]
14 if _sum<s: continue
15 while _sum >= s:
16 _sum -= nums[left]
17 left +=1
18 left -=1
19 _sum+=nums[left]
20
21 if i-left+1<_min:
22 _min = i-left+1
23 if _min == sys.maxint:
24 return 0
25 return _min
13def max_subarray(nums):
14 """
15 :type nums: List[int]
16 :rtype: int
17 """
18 currsum, maxn = 0, float('-inf')
19 for i in range(len(nums)):
20 if currsum + nums[i] > 0:
21 currsum += nums[i]
22 maxn = max(maxn, currsum)
23 else: # to get max of -ve integers
24 currsum = 0
25 maxn = max(maxn, nums[i])
26 return maxn
2def splitArray(self, nums, m):
3 """
4 :type nums: List[int]
5 :type m: int
6 :rtype: int
7 """
8 def cut(nums, mid, m):
9 count = 1
10 current_sum = 0
11 for num in nums:
12 current_sum += num
13 if current_sum > mid:
14 count += 1
15 current_sum = num
16 if count > m:
17 return False
18 return True
19
20 low = max(nums)
21 high = sum(nums)
22 while low <= high:
23 mid = (low + high) // 2
24 cuts = cut(nums, mid, m)
25 if cuts:
26 high = mid - 1
27 else:
28 low = mid + 1
29 return low
13def find_max_subarray2(numbers):
14 max_till_here = [numbers[0]]
15 for n in numbers[1:]:
16 max_till_here.append(max(n, max_till_here[-1] + n))
17 return max(max_till_here)
2def minSubArrayLen(self, s, nums):
3 """
4 :type s: int
5 :type nums: List[int]
6 :rtype: int
7 """
8
9 j = 0
10 res = float('inf')
11 sums = 0
12
13 for i in range(len(nums)):
14 while (j < len(nums) and sums < s):
15 sums += nums[j]
16 j += 1
17
18 if (sums >= s):
19 res = min(res, j - i)
20
21 sums -= nums[i]
22
23 return 0 if res == float('inf') else res
23def threeSum(self, nums):
24 """
25 :type nums: List[int]
26 :rtype: List[List[int]]
27 """
28 nums.sort()
29 res = []
30
31 for i in range(len(nums)-1): # because sums of 3 numbers
32 if i == 0 or i > 0 and nums[i-1] != nums[i]:
33 # avoid duplicate triplets [1 ,1, 1, -2]
34 left = i + 1
35 right = len(nums) - 1
36 while left < right: # two-way pointer
37 s = nums[i] + nums[left] + nums[right]
38 if s == 0:
39 res.append([nums[i], nums[left], nums[right]])
40 left += 1
41 right -= 1
42 while left < right and nums[left] == nums[left - 1]:
43 left += 1
44 while right > left and nums[right] == nums[right + 1]:
45 right -= 1
46 elif s < 0:
47 left += 1
48 else:
49 right -= 1
50 return res
2def arrayPairSum(self, nums):
3 """
4 https://leetcode.com/problems/array-partition-i/description/
5 :type nums: List[int]
6 :rtype: int
7 """
8 nums = sorted(nums)
9 sum = 0
10 for i in range(0,len(nums),2):
11 sum += nums[i]
12 return sum

Related snippets