服务好的郑州网站建设,吉安市规划建设局网站,男和男人怎么做那个视频网站,郑州模板网站建设策划公司题意
给我们一个二维矩阵 让我们在找出其中的最大子矩阵和
分析
对输入的一个矩阵 我们考虑一维线性矩阵 上的最大子段和 对于一个数串 我们的选择策略是
res max#xff08;res,max( suma[ i ], a[ i ] )#xff09;;
res就是最后我们得到的最大子段和的结果 a[i]是…题意
给我们一个二维矩阵 让我们在找出其中的最大子矩阵和
分析
对输入的一个矩阵 我们考虑一维线性矩阵 上的最大子段和 对于一个数串 我们的选择策略是
res maxres,max( suma[ i ], a[ i ] );
res就是最后我们得到的最大子段和的结果 a[i]是数串元素 我们这里可以把它压缩成一维 枚举任意两行 然后把两行之间的行压缩成1行 对这一行进行一维的最大字段和求解 所以最大子矩阵和就可以将二维中的任一一维压缩成一维 然后用一维最大字段和的 办法求解
关于一维最大字段和问题 /* b本可以设为数组 表示以第i个元素结尾的最大字段和是多少 也就是在b[i] max(b[i-1]dp[i],dp[i])中选择最大 这里就是两种选择 对于一个数串 为了求出最大子段和 我们可以选择累加 也可以选择扔掉前面的就取当前元素作为新子段的开始元素 选择累加前缀和 还是选择构造新子段 分别对应两种策略 两者取最优 若累加时表示能够正向让前缀和增大我们累加 若累加只能更小 我们选择扔掉时表示前面的元素 何时累加会变小 有两种情况 如果此时累加和为负数 如果新元素是个负数 负数相加只能更小 所以不如取一个更大的负数 如果新元素是个正数 那么不如就取当前元素 扔掉前面的 以上两种可能在前面累加和是负数的情况下 都选择max的后者为最优情况 所以当前面累加和为负数 直接扔掉 选后面的准没错 由于只用到前后两个元素所以可以节省空间用一个变量简略表示 */
code
#includeiostream
#includecstdio
#includealgorithm
#includecstring
using namespace std;
int n,dp[110],a[110][110];
int Max()
{int b 0,res-130;for(int i1;in;i){if(b0)bdp[i];// 表示能如果遇到正数还能继续递增else b dp[i];//如果是负数 由于负数只能越加越小 所以那么直接让他等于当前元素res max(res,b);//最优化结果}return res;
}
int main()
{scanf(%d,n);for(int i1;in;i){for(int j1;jn;j)scanf(%d,a[i][j]);}int res-130;for(int i1;in;i){for(int j i;jn;j){for(int k1;kn;k)dp[k]a[j][k];int ma Max();res max(ma,res); }memset(dp,0,sizeof(dp));}printf(%d\n,res);return 0;
}
