problem

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        if len(nums) == 1:
            return nums[0]

        max = nums[0]
        j = 0
        while True:
            if j >= len(nums) or nums[j] > 0:
                break

            if nums[j] > max:
                max = nums[j]
            j += 1

        tmp = 0
        for i in range(j, len(nums)):
            if nums[i] < 0:
                if tmp + nums[i] > 0:
                    tmp += nums[i]
                else:
                    tmp = 0
            else:
                tmp += nums[i]

            if tmp > max:
                max = tmp

        return max

anothor solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        max_ending_here, max_ending_sofar = nums[0], nums[0]
        for n in nums[1:]:
            max_ending_here = max(max_ending_here + n, n)
            max_ending_sofar = max(max_ending_sofar, max_ending_here)
        return max_ending_sofar

experience

虽然只是一个查找子串的问题，不过也挺有意思，还要再寻找下用dp怎么写。