10 examples of 'maximum frequent subarray sum' 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

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

67
def test_5(self):
68
    arr = [-1, -2, -3, -4, -5]
69
    self.assertEquals(120, self.solution.maxProduct(arr))

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

35
def topKFrequent2(self, nums, k):
36
    """
37
    :type nums: List[int]
38
    :type k: int
39
    :rtype: List[int]
40
    """
41
    import heapq
42
    m = {}
43
    for num in nums:
44
        if num not in m:
45
            m[num] = 1
46
        else:
47
            m[num] += 1
48
49
    lst = []
50
    for e in m:
51
        heapq.heappush(lst, (-m[e], e))
52
    res = []
53
    for i in range(k):
54
        res.append(heapq.heappop(lst)[1])
55
    return res

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

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

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

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)

3
def arrayNesting2(self, nums):
4
    sets, l = [], [0] * len(nums)
5
    for i in range(len(nums)):
6
        for s in sets:
7
            if nums[i] in s:
8
                l[i] = len(s)
9
                break
10
        if not l[i]:
11
            s = set()
12
            j = i
13
            while nums[j] not in s:
14
                s.add(nums[j])
15
                j = nums[j]
16
            l[i] = len(s)
17
            if len(s) > 1: sets.append(s)
18
    return max(l)