POJ 1050 / HDU 1081 To the Max（最大子矩阵和）-程序员宅基地

题目链接：

HDU：http://acm.hdu.edu.cn/showproblem.php?pid=1081

题意：给出一个n*n的矩阵，正负均有。求一个子矩阵使得该子矩阵的和尽可能的大。

思路：类似于最大子段和，即将前i行至前j行的矩阵压缩成一行，利用一个数组c，c[k]表示第k列从第i行到第j行的和，接下来只需对数组c求最大子段和，结果即为第i行到第j行中的最大子矩阵和。

代码：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 5e2 + 10;
const int INF = 0x3f3f3f3f;

long long a[N][N];
long long c[N];
int n, m;

long long getAns() {
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
      long long res = 0;
      for (int k = 1; k <= m; k++) {
        c[k] = (i == j ? a[i][k] : c[k] + a[j][k]);
        if (res < 0)
          res = c[k];
        else
          res = res + c[k];
        ans = max(res, ans);
      }
    }
  }
  return ans;
}

int main() {
  while (scanf("%d%d", &m, &n) != EOF) {
    long long _max = -INF;
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        scanf("%lld", &a[i][j]);
        _max = max(_max, a[i][j]);
      }
    }
    // 若矩阵全为负数，则认为结果为0
    long long ans = (_max < 0LL ? 0 : getAns());
    printf("%lld\n", ans);
  }
  return 0;
}

本文链接：https://blog.csdn.net/u014357885/article/details/52107058

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

python编码问题之encode、decode、codecs模块_python中encode在什么模块-程序员宅基地

文章浏览阅读2.1k次。原文链接先说说编解码问题编码转换时，通常需要以unicode作为中间编码，即先将其他编码的字符串解码（decode）成unicode，再从unicode编码（encode）成另一种编码。 Eg：str1.decode('gb2312') #将gb2312编码的字符串转换成unicode编码str2.encode('gb2312') #将unicode编码..._python中encode在什么模块

Java数据流-程序员宅基地

文章浏览阅读949次，点赞21次，收藏15次。本文介绍了Java中的数据输入流（DataInputStream）和数据输出流（DataOutputStream）的使用方法。

ie浏览器无法兼容的问题汇总_ie 浏览器 newdate-程序员宅基地

文章浏览阅读111次。ie无法兼容_ie 浏览器 newdate

想用K8s，还得先会Docker吗？其实完全没必要-程序员宅基地

文章浏览阅读239次。这篇文章把 Docker 和 K8s 的关系给大家做了一个解答，希望还在迟疑自己现有的知识储备能不能直接学 K8s 的，赶紧行动起来，K8s 是典型的入门有点难，后面越用越香。

ADI中文手册获取方法_adi 如何查看数据手册-程序员宅基地

文章浏览阅读561次。ADI中文手册获取方法_adi 如何查看数据手册

React 分页-程序员宅基地

文章浏览阅读1k次，点赞4次，收藏3次。React 获取接口数据实现分页效果以拼多多接口为例实现思路加载前加载动画加载后判断有内容的时候无内容的时候用到的知识点1、动画效果（用在加载前，加载之后就隐藏或关闭，用开关效果即可）2、axios请求3、map渲染页面4、分页插件（antd）代码实现import React, { Component } from 'react';//引入axiosimport axios from 'axios';//引入antd插件import { Pagination }_react 分页

随便推点

关于使用CryPtopp库进行RSA签名与验签的一些说明_cryptopp 签名-程序员宅基地

文章浏览阅读449次，点赞9次，收藏7次。这个变量与验签过程中的SignatureVerificationFilter::PUT_MESSAGE这个宏是对应的，SignatureVerificationFilter::PUT_MESSAGE，如果在签名过程中putMessage设置为true，则在验签过程中需要添加SignatureVerificationFilter::PUT_MESSAGE。项目中使用到了CryPtopp库进行RSA签名与验签，但是在使用过程中反复提示无效的数字签名。否则就会出现文章开头出现的数字签名无效。_cryptopp 签名