[LeetCode]easy - Maximum Subarray - python

题目要求：

从一个数组中找出一个子串使其和最大，是最大子串和问题。

Problem Description:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

题目链接

思路一：

暴力法，把每一个subarray的和都算一遍，记录其中出现的最大值。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_sum = nums[0]
        for i in range(0,len(nums)):
            current_sum = nums[i]
            if i != len(nums) - 1:
                for j  in range(i + 1, len(nums)):
                    if current_sum > max_sum:
                        max_sum = current_sum
                    current_sum = current_sum + nums[j]
            else:
                if nums[-1] > max_sum:
                    max_sum = nums[-1]
            if current_sum > max_sum:
                        max_sum = current_sum
        return max_sum

结果如下：

因为时间复杂度太高于是超时了（或者我写出bug了）

思路二：

给定的数组如果表示为 array[1…n]，假定array[i…j]是最大和的子串。对于数组中的每一个元素，它分为以下两种情况：加入之前的数组加和之中，或者自己成为一个子数组的开头。

动态规划状态转移方程：current_sum = max(nums[i], current_sum + nums[i])

然后我们一直记录最大的值即可。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        elif len(nums) == 1:
            return nums[0]
        else:
            current_sum = max_sum = nums[0]
            for i in range(1, len(nums)):
                current_sum = max(nums[i], current_sum + nums[i])
                max_sum = max(max_sum, current_sum)
            return max_sum

结果如下：

动态规划：

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。