1937. Maximum Number of Points with Cost

Time: O(mn)

Space: O(n)

Approach

DP row by row; left-right sweeps track running max to avoid O(n²) per row.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Dynamic Programming

Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.

1937.cs

// Approach: DP row by row; left-right sweeps track running max to avoid O(n²) per row.
// Time: O(mn) Space: O(n)

public class Solution
{
    public long MaxPoints(int[][] points)
    {
        int n = points[0].Length;

        long[] dp = new long[n];

        foreach (var row in points)
        {
            long[] leftToRight = new long[n];
            long runningMax = 0;

            for (int j = 0; j < n; ++j)
            {
                runningMax = Math.Max(runningMax - 1, dp[j]);
                leftToRight[j] = runningMax;
            }

            long[] rightToLeft = new long[n];
            runningMax = 0;

            for (int j = n - 1; j >= 0; --j)
            {
                runningMax = Math.Max(runningMax - 1, dp[j]);
                rightToLeft[j] = runningMax;
            }

            for (int j = 0; j < n; ++j)
                dp[j] = Math.Max(leftToRight[j], rightToLeft[j]) + row[j];
        }

        return dp.Max();
    }
}

Was this solution helpful?