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

9
def 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

22
def 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

4
def 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

2
def 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:
15
            _sum -= nums[left]
16
            left +=1
17
        left -=1
18
        _sum+=nums[left]
19
        
20
        if i-left+1<_min:
21
            _min = i-left+1
22
    if _min == sys.maxint:
23
        return 0
24
    return _min

13
def 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

2
def 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

13
def 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)

2
def 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

23
def 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

2
def 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