动态规划

• 最大子串和 Maximum Subarray

def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if len(nums) == 1:
        return nums[0]
    curMax = nums[0]
    globalMax = nums[0]
    for item in nums[1:]:
        if item + curMax > item:
            curMax = item + curMax
        else:
            curMax = item
        if curMax > globalMax:
            globalMax = curMax
    return globalMax

• 最长上升子序列Longest Increasing Subsequence

# O(n^2)的解法
class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        N = len(nums)
        if N <= 1:
            return N
        
        dp = [1] * N
        
        for i in range(1, N):
            for j in range(i):
                if nums[i] > nums[j] and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
        return max(dp)