最大子列和问题

问题：给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。

样例

给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6

算法1：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def maxSubArray(nums):
    max_num = nums[0]
    for i in range(len(nums)):
        this_sum = 0
        for j in range(i,len(nums)):
            this_sum += nums[j]
            if this_sum > max_num:
                max_num = this_sum
    return max_num

第一层循环负责子序列的起始位置，第二层循环负责子序列相加，每次相加都与最大值比较。当i=0 时，第二层循环遍历的子列和：nums[0],nums[0]+nums[1],...,nums[0]+nums[1]+...+nums[n] 。如果把max_num = 0 ，在序列全为负数时将出现错误，这时的输出为0，实际应为负数。因此，需要将最大值设为数组的第一位数字。

算法2：

思路：

如果 nums[i] 为负数，那么任何以 nums[i] 为起点的子序列都不可能是最大和的子序列，此时可以把 nums[i+1] 作为起点。同样，任何负的子序列也不可能作为最大和子序列的前缀，假设负的子序列为nums[i]...nums[j] ，那么可以将 nums[j+1] 作为起点。如果有以 nums[j] 结尾的某序列和是负数，表明这个序列中的任何一个数不可能是与 nums[j] 后面的数形成的最大子序列的开头，但是并不表明 nums[j] 前面的某个序列就不是最大序列，也就是说不能确定最大子序列在 nums[j] 前还是 nums[j] 后，即最大子序列位置不能求出。但是能确保maxSum的值是当前最大的子序列和。

定义两个变量，一个当前和，一个最大和。然后相邻的数字相加，如果当前和大于最大和，则将当前和赋值给最大和；如果当前和小于0，则舍弃当前和，将当前和赋值为0，因为如果当前和小于0，无论后面怎么加，都会减小子列和。

代码如下：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def maxSubArray(nums):
    this_sum = 0
    max_sum = nums[0]
    for i in range(len(nums)):
        this_sum += nums[i]
        #max_sum = max(this_num,max_num)
        if this_sum > max_sum:
            max_sum = this_sum
        #this_num = max(this_num,0)
        elif this_sum < 0:
            this_sum = 0
    return max_sum

类似可以求最小字数组

题目：

给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。

样例

给出数组[1, -1, -2, 1]，返回 -3

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def minSubArray(nums):
    this_sum = 0
    min_sum = nums[0]
    for i in range(len(nums)):
        this_sum += nums[i]
        #min_sum = min(this_num,max_num)
        if this_sum < min_sum:
            max_sum = this_sum
        #this_num = min(this_num,0)
        elif this_sum > 0:
            this_sum = 0
    return max_sum

源代码地址：https://github.com/ianxin/Algorithm/tree/master/src