本文共 895 字，大约阅读时间需要 2 分钟。

剑指offer—连续子数组的最大和

题目描述：给定一个输入数组，输出该数组的中所以子数组的和的最大值。时间复杂度为O（n）。

思路：

一、由于数组中有正有负，因此我们可以顺序遍历一般数组，依次累加每一个数字。如果累加到某一个数字i时的结果比他本身还小时，就说明前i-1个数字构成的子序列和还没有这一个数字i大。故将之前得到的和抛弃，选择当前数字i作为新的最大和，继续循环。这样值循环一次得到的结果复杂度当然为O（n）。

二、动态规划的方法：

递归公式为： $f(i)=\left\{ \begin{array}{ll} array[i] & i=0或者f(i-1)\leqslant0 \\ f(i-1)+array[i] & i\ne0并且f(i-1)>0 \end{array} \right.$ 以第i-1个数字结尾的子数组中所以数字的和小于0时，将这个和与第i个数字相加比第i个数字还要小时，此时第i个数字本身构成的字数组就为最大和。如果加上第i个数字比之前的和要大，当前最大和就为前i-1个数字的和加上i。

# -*- coding:utf-8 -*-class Solution:    def FindGreatestSumOfSubArray(self, array):        # write code here        arr_len = len(array)        sumtemp = 0        result = array[0]        for i in array:            if sumtemp > 0:                sumtemp += i            else:                sumtemp = i            if result < sumtemp:                result = sumtemp            return result

转载地址：http://vqmws.baihongyu.com/