python实现动态规划求解给定矩阵的和最大的子数组（矩阵中数字正负均存在）

本文主要是介绍python实现动态规划求解给定矩阵的和最大的子数组（矩阵中数字正负均存在），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

    本篇博文比较简单没有太多实际意义，只是为了练习一下，动态规划我并不熟悉，也是刚处于学习的阶段，这一篇博文是对上一篇博文的java代码转换成python，练习使用。

问题：

   给定一个指定的矩阵，维数小于1000，在矩阵的所有子数组中寻找具有最大和的子数组求和输出

思路：

    典型的动态规划问题

下面是具体的实现：

#!usr/bin/env python
#encoding:utf-8'''
__Author__:沂水寒城
功能：python动态规划求解矩阵中子列表最大和
'''def main_func():''''''rows=int(raw_input())cols=int(raw_input())matrix=[]num_list=[]for i in range(rows):matrix.append(['*']*cols)for i in range(rows):for j in range(cols):matrix[i][j]=int(raw_input())num_list+=matrix[i]dp=['*']*(rows*cols)dp[0]=num_list[0]for i in range(1,rows*cols):dp[i]=max(dp[i-1]+num_list[i],dp[i-1])print dpprint 'matrix中子数组最大和为：', dp[-1]if __name__ == '__main__':main_func()

结果如下：

这篇关于python实现动态规划求解给定矩阵的和最大的子数组（矩阵中数字正负均存在）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---