[Leetcode] 3363. Find the Maximum Number of Fruits Collected

https://leetcode.com/problems/find-the-maximum-number-of-fruits-collected/?envType=daily-question&envId=2025-08-07

initial

i thought it was bfs but its tricky

so i dont think its that hard. Impt thing is we can only take n-1 steps so first child MUST travel along the main diagonal.

The second and third child MUST take steps that do not cross the main dia and dia transpose. Cuz its geometrically imposs to reach the target grid within n-1 steps. So we should mark out the grids that are above these 2 diagonals with value 0 like below.

then its dp where for each grid, we look back at previous row (second child) or previous col(third child) to see which previous values are the max so as to traverse the best path.

we then add the [n-1][n2] (grids just before the target grid) cuz that dp value will store the best path traversed so far before reaching target grid.

sol

class Solution {
    public int maxCollectedFruits(int[][] fruits) {
        int n=fruits.length;
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(j>i && j<n-1-i){
                    fruits[i][j]=0;
                }
                if(i>j && i<n-1-j){
                    fruits[i][j]=0;
                }
            }
        }
        for(int i=0;i<n;i++){
            ans+= fruits[i][i];
        }
        for(int i=1;i<n;i++){
            for(int j=i+1;j<n;j++){
                fruits[i][j] += Math.max(fruits[i-1][j-1], Math.max(fruits[i-1][j], (j+1<n) ?fruits[i-1][j+1] :0));
            }
        }
        for(int j=1;j<n;j++){
            for(int i=j+1;i<n;i++){
                fruits[i][j] +=Math.max(fruits[i-1][j-1],Math.max(fruits[i][j-1], (i+1<n) ? fruits[i+1][j-1] :0));
            }
        }
        return ans+fruits[n-1][n-2]+fruits[n-2][n-1];
    }
}

complexity

n^2 time
1 space