report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
  • Problem
  • Submit
  • Results
Maximum submatrix sum - MarisaOJ: Marisa Online Judge

Maximum submatrix sum

Time limit: 1000 ms
Memory limit: 256 MB
You are given a 2D integer array $A$ of size $n \times m$. Find a submatrix with maximum sum. ### Input - The first line contains 2 integers $n, m$. - Each line in the next $n$ lines contains $m$ integers $A_{i, j}$. ### Output - A single integers, the maximum sum. ### Constraints - $1 \le n, m \le 500$. - $|A_{i,j}| \le 10^9$. ### Example Input: ``` 2 3 1 -4 3 2 2 -3 ``` Output: ``` 4 ```
Introduction to Prefix sum
Prefix sum
Maximum subarray sum
Balance substring
Divisible by d
Subarray sum
Game on array
2D prefix sum
Stair query
Maximum sum subarray 2
Average
Ratio Substrings
Maximum submatrix sum
Maximum subarray sum 3
Manhattan distance
Minimum distance
Topic
Prefix sum
Rating 1200
Solution (1) Solution