Capped Max Submatrix Problem

Capped Max Submatrix Problem — ExecCode Hard DSA Practice

Solve the Capped Max Submatrix problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Find a contiguous submatrix whose sum is as large as possible without exceeding cap k. This mixes 2D Kadane (fix left/right columns, compress to a 1D array of row sums) with 'largest prefix not exceeding a bound'. It is harder than 1D maximum subarray and shows up in OA hard sets. Return that maximum sum that is <= k. The matrix is guaranteed to have at least one submatrix with sum <= k. You are given: matrix — 2D integers, possibly negative k — upper bound on the sum Return integer best sum <= k. A 1×1 cell is a valid submatrix.

Examples

Input {'matrix': [[1, 0, 1], [0, -2, 3]], 'k': 2}; Output 2. Input {'matrix': [[2, 2, -1]], 'k': 3}; Output 3. Input {'matrix': [[5, -4, 3]], 'k': 4}; Output 4

Constraints

Empty submatrix is not allowed k may be smaller than some individual cells; then those cells cannot be chosen alone if they exceed k

Practice Capped Max Submatrix free on ExecCode. Browse DSA problems, topic map, and placement guides.