JZ42 连续子数组的最大和

解题思路

方法1：连续的子数组，即数组中从i下标到j下标（0<=i<=j<数组长度）的数据，想要获得所有的子数组和，可以通过暴力法，两次循环获得，但时间复杂度为O(n^2)，效率不高。

方法2：动态规划，设动态规划列表 dp，dp[i] 代表以元素 array[i] 为结尾的连续子数组最大和。
状态转移方程： dp[i] = Math.max(dp[i-1]+array[i], array[i]);
具体思路如下：
1.遍历数组，比较 dp[i-1] + array[i] 和 array[i]的大小;
2.为了保证子数组的和最大，每次比较 sum 都取两者的最大值;
3.用max变量记录计算过程中产生的最大的连续和dp[i]；

方法3：我们可以简化动态规划，使用一个变量sum来表示当前连续的子数组和，以及一个变量max来表示中间出现的最大的和。

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        ans = array[0]
        sum_ = 0
        for i in range(len(array)):
            sum_ = 0
            for j in range(i,len(array)):
                sum_ += array[j]
                ans = max(ans,sum_)
        return ans

方法2：动态规划，时间复杂度O(n)，空间复杂度O(n)

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        length = len(array)
        dp  =[0]*(length+1)
        dp[0] = 0
        sum_ = 0
        ret = array[0]
        for i in range(1,length+1):
            sum_ = max(array[i-1],sum_+array[i-1])
            ret = max(ret,sum_)
        return ret

方法3：优化动态规划，时间复杂度O(n)，空间复杂度O(1)

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        length = len(array)
        dp  =[0]*(length)
        dp[0] = 0
        sum_ = 0
        ret = array[0]
        for i in range(0,length):
            sum_ = max(array[i],sum_+array[i])
            ret = max(ret,sum_)
        return ret