max-submatrix-lcci

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。

英文版：Cracking the Coding Interview，源自硅谷程序员的面试红宝书

LCCI

Given an NxM matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.

Return an array&nbsp;<code>[r1, c1, r2, c2]</code>, where&nbsp;<code>r1</code>, <code>c1</code> are the row number and the column number of the submatrix&#39;s upper left corner respectively, and&nbsp;<code>r2</code>, <code>c2</code> are the row number of and the column number of lower right corner. If there are more than one answers, return any one of them.

Note:&nbsp;This problem is slightly different from the original one in the book.

Example:

<pre>
Input:
<code>[
&nbsp; [-1,0],
&nbsp; [0,-1]
]</code>
Output: [0,1,0,1]</pre>

Note: 

<ul>
	<li><code>1 &lt;= matrix.length, matrix[0].length &lt;= 200</code></li>
</ul>

getMaxMatrix

Max Submatrix LCCI

Array

Dynamic Programming

Matrix

Prefix Sum

给定一个正整数、负整数和 0 组成的 N &times; M&nbsp;矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 <code>[r1, c1, r2, c2]</code>，其中 <code>r1</code>, <code>c1</code> 分别代表子矩阵左上角的行号和列号，<code>r2</code>, <code>c2</code> 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

注意：本题相对书上原题稍作改动

示例：

<pre>输入：
<code>[
&nbsp; [-1,0],
&nbsp; [0,-1]
]</code>
输出：[0,1,0,1]
解释：输入中标粗的元素即为输出所表示的矩阵</pre>

&nbsp;

说明：

<ul>
	<li><code>1 &lt;= matrix.length, matrix[0].length &lt;= 200</code></li>
</ul>