Back
Close
  • 25

What will I learn?

Dynamic programming

Statement

 Goal

Given a 2D array of positive and negative integers, try finding out the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all its elements. A sub-rectangle can be of any size from 1x1 to the max area of the whole rectangle, and can be located anywhere within the whole rectangle.
Input
Line 1: W H for the width and height of the whole rectangle
Next H lines: space separated integers. Each line contains one row of data for the rectangle
Output
The sum of the "maximum" sub-rectangle
Constraints
1 ≤ W, H ≤ 100
-99 ≤ n ≤ 99, where n is any integer within the rectangle
No data line is longer than 500 characters
Example
Input
2 2
5 -9
6 9
Output
15
Solve it

A higher resolution is required to access the IDE

Online Participants