Collect Max Points

Find the maximum points a kid can collect while navigating through an M×N matrix where movement is restricted to right, top-right, or bottom-right directions.

Understand the Problem

Problem Statement

Collect Max Points: A kids game has a board with an M×N matrix having M rows and N columns containing non-negative integer values as cell values. The kid can start from the first column of any row and can perform the following three navigations after collecting the points in that cell.

He can move to the right cell.
He can move to the top right cell.
He can move to the bottom right cell.

The kid cannot come back to a previous column. He navigates until he reaches the last column of the matrix and collects the points in each cell. The program must print the maximum points a kid can collect for the given matrix while navigating.

Constraints

2 ≤ M, N ≤ 30
Matrix values are non-negative integers
Start from any cell in the first column
Move only right, top-right, or bottom-right
Cannot move to previous columns

Examples

Example 1

Input

Output

Explanation

The maximum points can be collected by navigating 2→9→4 (starting from row 2, col 0). The sum is 2+9+4 = 15. Other possible paths like 5→3→3=11 or 5→1→4=10 yield lower sums.

Example 2

Input

Output

Explanation

The maximum points 16 can be collected by navigating 5→6→2→3 (starting from row 3, col 0) or 5→2→4→5 (starting from row 3, col 0). Both paths yield sum 16.

Solution

#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) {
    return (a > b) ? a : b;
}

int main() {
    int M, N;
    scanf("%d %d", &M, &N);
    
    int matrix[M][N];
    
    // Read matrix values
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    
    // Dynamic programming: fill matrix with maximum points
    for (int j = 1; j < N; j++) {
        for (int i = 0; i < M; i++) {
            if (i == 0) {
                // Top row: can come from left or bottom-left
                matrix[i][j] += max(matrix[i][j-1], matrix[i+1][j-1]);
            } else if (i == M-1) {
                // Bottom row: can come from left or top-left
                matrix[i][j] += max(matrix[i][j-1], matrix[i-1][j-1]);
            } else {
                // Middle rows: can come from top-left, left, or bottom-left
                int maxPrev = max(matrix[i-1][j-1], matrix[i][j-1]);
                maxPrev = max(maxPrev, matrix[i+1][j-1]);
                matrix[i][j] += maxPrev;
            }
        }
    }
    
    // Find maximum in last column
    int maxPoints = matrix[0][N-1];
    for (int i = 1; i < M; i++) {
        if (matrix[i][N-1] > maxPoints) {
            maxPoints = matrix[i][N-1];
        }
    }
    
    printf("%d\n", maxPoints);
    
    return 0;
}

Time:O(M×N) - We process each cell exactly once

Space:O(1) - We modify the input matrix in-place, no additional space required

Approach:

C Solution Explanation:

Input Reading: Read M and N, then read the M×N matrix values into a 2D array.
Dynamic Programming: For each column from left to right, update each cell by adding the maximum value from the three possible previous positions.
Edge Handling: Use conditional logic to handle top and bottom rows that have fewer possible previous positions.
Result Extraction: Find the maximum value in the last column, which represents the maximum points collectable.

The solution modifies the matrix in-place to store cumulative maximum points at each position.

Visual Explanation

Loading diagram...

All Problems