【剑指offer】连续子数组的最大和（python）

1. python初始化整数的最大值和最小值
   

这是聪明法，这个sum的设置，想不到

# -*- coding:utf-8 -*-
import sys
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if not array: return 0
        sum = 0
        maxSum = -sys.maxint -1
        for i in array:
            sum = i if sum <=0 else sum+i
            maxSum = max(maxSum, sum)
        return maxSum

2. 用动规，暴力解
   状态定义：dp[i]表示以第i个数字结尾的连续子数组的最大和。
   状态转移方程：dp[i] = max(array[i], dp[i-1]+array[i])。如果当前元素为整数，并且dp[i-1]为负数，负数越加越小，结果就是只选当前元素。
   技巧：这里为了统一代码的书写，定义dp[i]表示前i个元素的连续子数组的最大和，结尾元素为array[i-1]

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