【Python】给定一个数组A[0,…,n-1]，求A的连续子数组，使得该子数组的和最大

た入场券 2022-05-22 10:05 163阅读 0赞

# 最大子数组 #

> 给定一个数组A\[0,…,n-1\]，求A的连续子数组，使得该子数组的和最大。  
> 例如数组： 1, -2, 3, 10, -4, 7, 2, -5  
> 最大子数组：3, 10, -4, 7, 2

## 算法分析 ##

定义：前缀和sum\[i\] = a\[0\] + a\[1\] + …+a\[i\]  
则：a\[i,j\]=sum\[j\]-sum\[i-1\](定义sum\[-1\] = 0)  
算法过程  
1. 求i前缀sum\[i\]：  
遍历i：0≤i≤n-1  
sum\[i\]=sum\[i-1\]+a\[i\]  
2. 计算以a\[i\]结尾的子数组的最大值对于某个i：遍历0≤j≤i，求sum\[j\]的最小值m  
sum\[i\]-m即为以a\[i\]结尾的数组中最大的子数组的值  
3. 统计sum\[i\]-m的最大值， 0≤i≤n-1  
1、2、3步都是线性的，因此，时间复杂度O(n)。

### 进一步的分析 ###

记S\[i\]为以A\[i\]结尾的数组中和最大的子数组  
则：S\[i+1\] = max(S\[i\]+A\[i+1\], A\[i+1\])  
S\[0\]=A\[0\]  
遍历i： 0≤i≤n-1  
动态规划：最优子问题  
时间复杂度：O(n)

## Python代码 ##

# 输出最大子数组的和
    def max_subarray(li):
        if li is None or len(li) == 0:
            return 0
        s = li[0]  # 当前子串的和
        result = s  # 当前找到的最优解
        for i in range(len(li)):
            if s > 0:
                s += li[i]
            else:
                s = li[i]
            result = max(s, result)
        return result
    
    
    # 除了输出最大子数组的和，还需要输出最大子数组本身
    def max_subarray2(li):
        if li is None or len(li) == 0:
            return 0
        s = li[0]  # 当前子串的和
        result = s  # 当前找到的最优解
        fromIndex = toIndex = 0  # from=to=0
        fromIndexNew = 0  # 新的子数组起点
        for i in range(len(li)):
            if s > 0:
                s += li[i]
            else:
                s = li[i]
                fromIndexNew = i
            if result < s:
                result = s
                fromIndex = fromIndexNew
                toIndex = i
        print(li[fromIndex:toIndex + 1])
        return result
    
    
    if __name__ == '__main__':
        li = [1, -2, 3, 10, -4, 7, 2, -5]
        result = max_subarray2(li)
        print(result)

输出结果：  
\[3, 10, -4, 7, 2\]  
18