Optimal Frame Selection Path
At Lenskart, we're constantly innovating to provide the best customer experience, both online and in-store. Our AI-powered styling assistant helps customers discover frames that best suit their preferences. This system often presents a curated selection of frames in a grid-like interface. To optimize the customer's journey through this selection, we need to identify the most engaging path, maximizing their overall satisfaction.
You are tasked with implementing a function that calculates the maximum possible "customer satisfaction score" a customer can achieve by navigating through a grid of frames.
Given a 2D array (grid) representing frames, where frames[r][c] is the satisfaction score associated with the frame at row r and column c:
(r, c), the customer can only move to a frame in the next row (r+1) at one of the following relative column positions: c-1, c, or c+1 (if valid).R-1) is selected.Input:
frames: A 2D array of integers, frames[r][c], representing the satisfaction score for the frame at row r and column c.Output:
Examples
Example 1
Input:
frames = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output:
18
Note:
The path frames[0][2](3) -> frames[1][2](6) -> frames[2][2](9) yields a total score of 3 + 6 + 9 = 18. This is the maximum possible path sum.
Example 2
Input:
frames = [[-10, -5, -1], [-20, -15, -12], [-30, -25, -22]]
Output:
-35
Note:
The path frames[0][2](-1) -> frames[1][2](-12) -> frames[2][2](-22) yields -1 + (-12) + (-22) = -35. This is the maximum possible score, as maximizing with negative numbers means choosing the path with the smallest absolute sum.
Example 3
Input:
frames = [[10], [5], [12]]
Output:
27
Note:
With a single column, there is only one possible path: frames[0][0](10) -> frames[1][0](5) -> frames[2][0](12). The total score is 10 + 5 + 12 = 27.
Constraints
1 <= R (number of rows) <= 5001 <= C (number of columns) <= 500-100 <= frames[r][c] <= 100 (Satisfaction scores can be negative, indicating a poor fit or undesirable frame.)Loading editor...