动态规划:最大m子段和 python

标签: 动态规划

大家好,我是连人。本次接上期 最大子段和及最大子矩阵和问题继续讲最大m子段和问题。

在最大m子段和问题中,要求取m个互不相交子段,和为最大值。最大m子段和问题是最大子段和在子段个数上的推广,最大子段和问题是m=1的特殊情况。

在这个问题中,我们使用一个矩阵b[ i ][ j ],他表示的意义是在前 j 项中被分为 i 段的最大 i 子段和。

在这里插入图片描述

首先,既然是前 j 项需要分为 i 段,所以当 i == j 的时候,数组中的每个数自为一段,此时的值就是前 j 项的和。所以对角线上的值就是前 j 项加起来。

剩下的情况如下图:
在这里插入图片描述

若要确定蓝色块的值,则在黄色块中寻找一个最大值,与红色块比较,取大者加在自身上。

若是黄色块,当前值则是一个新的子段的开始。若是红色块,当前值是和前一个值一起组合成一个子段的。

若要找分为4段的值,则在第4行找最大值即可。

因为所有值是通过左上方或左方而来,所以为了节省时间和空间,可以将b矩阵按如下简化:
在这里插入图片描述

代码如下:

def max_sum_3(m, n, a):
    if n < m or m < 1:
        return
    b = []
    for i in range(0, m + 1):
        b.append([])
        for j in range(0, n + 1):
            b[i].append(0)
    for i in range(1, m + 1):
        for j in range(i, n - m + i):
            if j > i:
                b[i][j] = b[i][j-1] + a[j]
                for k in range(i - 1, j):
                    if b[i][j] < b[i-1][k] + a[j]:
                        b[i][j] = b[i-1][k] + a[j]
            else:
                b[i][j] = b[i-1][j-1] + a[j]
    sum = 0
    for j in range(m, n + 1):
        if sum < b[m][j]:
            sum = b[m][j]
    return sum

跟最大子段和问题类似,在最大子段和问题中,只用到了b[j]和b[j-1],因此只使用一个b来节约空间。同样地,在最大m子段和问题中,只使用了j行和j-1行,因此使用两个数组即可。

更改后的代码如下:

def max_sum_4(m, n, a):
    if n < m or m < 1:
        return
    b = []
    c = []
    for i in range(0, n - m + 1):
        b.append(0)
        c.append(0)
    for i in range(0, m):
        b[0] = c[0] + a[i]
        for j in range(1, n - m + 1):
            b[j] = b[j - 1] + a[i + j]
            for k in range(0, j + 1):
                if b[j] < c[k] + a[i + j]:
                    b[j] = c[k] + a[i + j]
        for j in range(0, n - m + 1):
            c[j] = b[j]
    sum = 0
    for i in range(0, n - m + 1):
        if sum < b[i]:
            sum = b[i]
    return sum

转载注明出处。

版权声明:本文为mirocky原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/mirocky/article/details/104163844