【左神算法课】二维矩阵的子矩阵最大累加和

题目描述:

思路描述(请结合后面的程序配套理解):

 代码:

 1 /*
 2 本程序说明:
 3 
 4 给定一个矩阵matrix,其中有正有负有0,返回子矩阵的最大累加和
 5 例如矩阵matrix为:
 6 -90 48 78
 7 64 -40 64
 8 -81 -7 66
 9 其中最大累加和的子矩阵为
10 48 78
11 -40 64
12 -7 66
13 
14 */
15 #include <iostream>
16 #include <vector>
17 using namespace std;
18 
19 int SubMatrixMaxSum(const vector<vector<int> >& matrix)
20 {
21     int max_sum=0;
22     for(size_t i=0;i<matrix.size();++i)
23     {
24         vector<int> s(matrix[0].size());
25         for(size_t j=i;j<matrix[0].size();++j)
26         {
27             int sum_cur=0;
28             for(size_t k=0;k<matrix[0].size();++k)
29             {
30                 s[k]+=matrix[j][k];
31                 sum_cur+=s[k];
32                 sum_cur=sum_cur<0 ? 0 : sum_cur;
33                 max_sum=max(max_sum,sum_cur);
34             }
35         }
36     }
37     return max_sum;
38 }
39 
40 int main()
41 {
42     vector<vector<int> > matrix{{-90,48,78},{64,-40,64},{-81,-7,66}};43     cout<<SubMatrixMaxSum(matrix)<<endl;
44     return 0;
45 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人人都是极客

5.训练模型之利用训练的模型识别物体

接下来我们开始训练,这里要做三件事: 将训练数据上传到训练服务器,开始训练。 将训练过程可视化。 导出训练结果导出为可用作推导的模型文件。 配置 Pipelin...

45340
来自专栏Petrichor的专栏

tensorflow: 畅玩tensorboard图表(SCALARS)

这篇博客建立在你已经会使用tensorboard的基础上。如果你还不会记录数据并使用tensorboard,请移步我之前的另一篇博客:tensorflow: t...

41530
来自专栏李智的专栏

Python中对文件夹下的特定格式图像全部读取并转化为数组保存(也可转化为txt文件)

python下对图像进行批处理少不了读取文件夹下的全部图像,下面就以具体实例分享下对文件夹下的特定格式图像全部读取并转化为数组保存的代码,代码详解请见注释 ...

44220
来自专栏AI研习社

Github 项目推荐 | GAN 非平稳纹理合成

该库是论文「Non-stationary texture synthesis using adversarial expansions.」的官方代码。

14030
来自专栏红色石头的机器学习之路

Coursera吴恩达《优化深度神经网络》课程笔记(3)-- 超参数调试、Batch正则化和编程框架

上节课我们主要介绍了深度神经网络的优化算法。包括对原始数据集进行分割,使用mini-batch gradient descent。然后介绍了指数加权平均(Exp...

54900
来自专栏漫漫深度学习路

MXNET学习笔记(一):Module类(1)

Module 是 mxnet 提供给用户的一个高级封装的类。有了它,我们可以很容易的来训练模型。 Module 包含以下单元的一个 wraper symbol ...

33050
来自专栏ASP.NET MVC5 后台权限管理系统

ASP.NET MVC5+EF6+EasyUI 后台管理系统(38)-Easyui-accordion+tree漂亮的菜单导航

本节主要知识点是easyui 的手风琴加树结构做菜单导航 有园友抱怨原来菜单非常难看,但是基于原有树形无限级别的设计,没有办法只能已树形展示 先来看原来的效果 ...

45660
来自专栏Jack-Cui

Caffe学习笔记(五):使用pycaffe生成solver.prototxt文件并进行训练

Python版本: Python2.7 运行平台: Ubuntu14.04     上几篇笔记记录了如何将图片数据转换成db(leveldb/lmdb)文件,...

41700
来自专栏量化投资与机器学习

【机器学习】支持向量机的概念与运用初探

? ? ? ? ? 下面,使用python模块库sklearn自带的iris标准数据集进行简单测试。 ? 获得的分类图为: ? 此外,尝试在优矿平台上,...

23180
来自专栏人工智能LeadAI

YOLO:实时目标检测

一瞥(You Only Look Once, YOLO),是检测Pascal VOC(http://host.robots.ox.ac.uk:8080/pasc...

1.2K70

扫码关注云+社区

领取腾讯云代金券