# Path of Optimum Grid Harvestby Isai Damier, Android Engineer @ Google

```/*********************************************************************
* Author: Isai Damier
* Title:  Path of Optimum Grid Harvest
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
*   Given n boxes of avocados tightly arranged in a h*w grid, and given
*   that you may only move down or to the right, amass the maximum
*   number of avocados and show the path taken.
*
* Time-complexity: O(n)
*
* Dynamic Programming Strategy:
*
*   The solution to this problem is exactly as describe in the Optimum
*   Grid Harvest implementation -- plus one more step.
*   http://www.geekviewpoint.com/java/dynamic_programming/grid_harvest.
*
*   To find the optimum number of avocados we keep moving down and
*   to the right from the first cell A to the last cell A[h][w].
*   For the second phase, to find the optimal path, simply do the reverse
*   with V[1..h][1..w]. That is, we walk from V[h][w] to V by
*   moving left and up, always toward the maximum.
*
**********************************************************************/
public List<Integer> gridHarvestPath(int[][] grid) {

if (null == grid) {
return null;
}
//exactly as simple gridHarvest problem
int[][] value = new int[grid.length][grid.length];
int xMax = grid.length - 1;
int yMax = grid.length - 1;
for (int x = 0; x <= xMax; x++) {
for (int y = 0; y <= yMax; y++) {
amass(grid, x, y, value);
}
}

//trace the boxes selected
List<Integer> path = new ArrayList<Integer>();
int x = xMax;
int y = yMax;
while (x > 0 && y > 0) {
if (value[x][y - 1] < value[x - 1][y]) {
} else {
}
}

while(x > 0){
}
while(y > 0){
}
return path;
}

private void amass(int[][] grid, int x, int y, int[][] value) {
if (0 < x && 0 < y) {
value[x][y] = grid[x][y] + Math.max(value[x - 1][y], value[x][y - 1]);
} else if (0 < x) {
value[x][y] = grid[x][y] + value[x - 1][y];
} else if (0 < y) {
value[x][y] = grid[x][y] + value[x][y - 1];
} else {
value[x][y] = grid[x][y];
}
}```
```package algorithm.programming.dynamic;

import java.util.Arrays;
import java.util.List;
import org.junit.Test;
import static org.junit.Assert.*;

public class HarvestingTest {

/**
* Test of gridHarvestPath method, of class Harvesting.
*/
@Test
public void testGridHarvestStaircasePath() {
System.out.println("gridHarvestPath");
int[][] grid = {
{51, 42, 33, 25, 18},
{13, 21, 34, 55, 89},
{82, 63, 45, 27, 11},
{13, 17, 19, 23, 29}
};
Harvesting instance = new Harvesting();
List expResult = Arrays.asList(29,11,89,55,34,33,42,51);
List result = instance.gridHarvestPath(grid);
assertEquals(expResult, result);
}

/**
* Test of gridHarvestPath method, of class Harvesting.
*/
@Test
public void testGridHarvest7Path() {
System.out.println("gridHarvestPath");
int[][] grid = {
{51, 92, 93, 97, 98},
{13, 21, 34, 55, 89},
{82, 63, 45, 27, 11},
{13, 17, 19, 23, 29}
};
Harvesting instance = new Harvesting();
List expResult = Arrays.asList(29,11,89,98,97,93,92,51);
List result = instance.gridHarvestPath(grid);
assertEquals(expResult, result);
}

/**
* Test of gridHarvestPath method, of class Harvesting.
*/
@Test
public void testGridHarvestLPath() {
System.out.println("gridHarvestPath");
int[][] grid = {
{51, 42, 33, 25, 18},
{93, 21, 34, 55, 89},
{92, 63, 45, 17, 11},
{93, 67, 59, 23, 29}
};
Harvesting instance = new Harvesting();
List expResult = Arrays.asList(29,23,59,67,93,92,93,51);
List result = instance.gridHarvestPath(grid);
assertEquals(expResult, result);
}
}```