题目一:
给定一个整型数组,数组中有正有负,求最大连续子序列的和。
解法:
利用动态规划的思想。
设f(n)表示以a[n]为子序列最后一个元素的最大和,则可以有下面的规则:
(1)当f(n-1)<0时,f(n)=a[n];
(2)当n!=0且f(n-1)>0时,f(n)=f(n-1)+a[n]。
用一个nGreatestNum来记录最大值,每次与f(n)进行比较,不断更新即可。
题目二:
给定一个二维数组,数组中有正有负,求最大子矩阵的和。
解法:
仍然用动态规划的思想。
首先,将二维问题降维处理:
例如,用2 维数组a[1 : m][1 : n]表示给定的m行n列的整数矩阵。子数组a[i1 : i2][j1 : j2]表示左上角和右下角行列坐标分别为(i1, j1)和(i2, j2)的子矩阵。
先按照行排列出所有可能区间,然后,再去求列的范围。
更详细的,当行区间确定之后,剩下就是确定列区间了,一旦确定列区间,最大子矩阵就确定了。
当行区间确定之后,求列区间的方法,可以转化成一维数组的最大连续子序列的问题:对行区间[i1, j1],依次对列进行求和,就得到n个数据的以为数组,根据最大连续子序列的和的求法,就可以获得连续子序列最大和。
仍然用nGreatestNum来记录最大值,算出一个子矩阵的和,就进行比较即可。
复杂度分析:
(1)排列出行区间,复杂度为O(M*M);
(2)而求得最大子序列的和复杂度为O(N);
(3)对于行区间确定之后对列求和的复杂度呢?
这里采用“部分和”的做法。
用BC[i][j]表示0到i行、0到j列的总和。
那么对于行区间r->l,求第i列的和:BC[l][i] - B[r-1][i] - B[l][i-1] + B[r-1][i-1]。
而求“部分和”仅需要O(N*M)。可以预先计算好。
因此,算法复杂度为O(N*M*M)。
相关推荐
给定一个二维数组,由其中若干邻近元素构成的矩形称为子数组,请编写程序计算所有子数组元素之和的最大值。 【输入数据】第一行为整数N,代表二维数组的大小为N*N。接下来的N*N个整数被空格和换行符隔开,表示按照行...
二维数组首尾相连,上下也相连,像个游泳圈或轮胎,又如何求最大子矩阵和? 如游泳圈展开成3行3列的二维矩阵: -18 10 7 1 -20 2 1 38 -2 那么最大的子矩阵和为:10+7+38-2=53 2 10 7 1 -20 2 1 38 -2 那么最大...
最大子矩阵和问题.pdf最大子矩阵和问题.pdf最大子矩阵和问题.pdf最大子矩阵和问题.pdf 详细分析和源码 值得好好研究啊
该代码具体实现了对于最大子矩阵问题利用动态规划的思路解决。
最大子矩阵是指在一个二维矩阵中,找到一个具有最大和的连续子矩阵。这个问题在计算机科学中有着广泛的应用,特别是在图像处理、数据分析和最优化问题中。 最大子矩阵问题可以被看作是最大子数组问题的二维版本。最...
最大子矩阵
最大子矩阵和,使用动态规划算法,c++语言编写,题目的肇庆学院oj-1948题
二维数组首尾相连,上下也相连,像个游泳圈或轮胎,又如何求最大子矩阵和? 如游泳圈展开成3行3列的二维矩阵: -18 10 7 1 -20 2 1 38 -2 那么最大的子矩阵和为:10+7+38-2=53 2 10 7 1 -20 2 1 38 -2 那么最大的...
问题:给定N×N矩阵,矩阵元素都是-127到+127之间的整数。请找到一个子矩阵,使得其元素之和最大。 输入: 第一行整数 N (N)。接下来N行元素,每行N个元素,每个元素介于-127到127之间。
问题:给定1×N的单行矩阵,矩阵每个元素都是-127到+127之间的整数。请找到一个连续子矩阵,使得其元素之和最大。 输入:整数 N (N),及N个元素。
最大子矩阵 C++实现的最大子矩阵和 C++实现的最大子矩阵和 C++实现的最大子矩阵和 C++实现的最大子矩阵和 C++实现的最大子矩阵和 C++实现的最大子矩阵和
最大子矩阵最大子矩阵.pdf最大子矩阵.pdf
用于求解最大子矩阵问题的一个程序,运用了动态规划,是最大字段和的升级版
3. 学会如何利用动态规划算法求解具体问题,了解动态规划算法的局限性。 1. 将矩阵的某一行看成一个序列,设计算法求该序列的最大子序列。 2. 将矩阵相邻两行对应列的元素相加形成一个新的序列,试分析该子序列中每-...
最大子矩阵
最大子矩阵最大子矩阵.zip最大子矩阵.zip
最大子矩阵 最大子矩阵_使用C++实现的最大子矩阵求和
最大子矩阵
最大子矩阵问题是一个经典的优化问题,其目标是在一个给定的矩阵中找到一个子矩阵,使得该子矩阵的元素和最大。这个问题可以看作是一维最大子序列和问题的扩展,从一维变为了二维。