Dynamic programming algorithm for n x n matrix of integers to find maximum sum

Question

I am having quite difficulty to understand the following question, if some one can please help me out understanding it, I will be very grateful. The question is:

Implement a dynamic programming algorithm for solving the following
problem. The input is an n × n matrix of integers. For the output: 
compute the largest sum of adjacent entries in horizontal, vertical,
diagonal and anti-diagonal direction. Return as output the sum 
h + v + d + c (in suggestive notation) of those four auxiliary results.
The largest (or maximal) sum of an array consisting of only negative  
integers is 0; that is, in that case we select the empty subarray.
A (small) example input matrix with solution 45:
|-2 5 3 2|
|9 -6 5 3|
|1 -8 2 -3|
|-1 2 -5 2|

I mean if some one can please help me towards the right direction,I will be really grateful!!! Thanks

Answer 1

Given your problem statement:

Implement a dynamic programming algorithm for solving the following problem. The input is an n × n matrix of integers. For the output: compute the largest sum of adjacent entries in horizontal, vertical, diagonal and anti-diagonal direction. Return as output the sum h + v + d + c (in suggestive notation) of those four auxiliary results. The largest (or maximal) sum of an array consisting of only negative
integers is 0; that is, in that case we select the empty subarray. A (small) example input matrix with solution 45:

|-2 5 3 2|
|9 -6 5 3|
|1 -8 2 -3|
|-1 2 -5 2|

Then, reading the example input you posted, I made a short method to parse that info from file:

public static List<List<Integer>> readFile(final String path) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    Path p = Paths.get(path);
    if (!Files.exists(p))
        return null;
    List<String> lines = null;
    try {
        lines = Files.readAllLines(p);
    } catch (IOException e) {
        e.printStackTrace();
    }
    if (lines == null)
        return null;
    for (String str : lines) {
        List<Integer> row = new ArrayList<Integer>();
        final String line = str.substring(1, str.length() - 1);
        String[] arr = line.split(" ");
        for (String s : arr)
            row.add(Integer.valueOf(s.trim()));
        result.add(row);
    }
    return result;
}

The vertical approach is straight forward, looping through nested array.

    public static int getVertical(final List<List<Integer>> list) {
        int result = 0;
        for (List<Integer> arr : list) {
            int curr = 0;
            for (Integer val : arr)
                curr += val;
            if (curr > result)
                result = curr;
        }
        return result;
    }

And the horizontal is also quite straight forward. Note: here I just used a list of counters for simplicity sake. There are more efficient approaches.

    public static int getHorizontal(final List<List<Integer>> list, final int len) {
        List<Integer> sums = new ArrayList<Integer>(list.get(0));
        for (int i = 1; i < len; ++i)
            for (int j = 0; j < len; ++j)
                sums.set(j, sums.get(j) + list.get(i).get(j));
        return Collections.max(sums);
    }

I quickly searched to find a diag/anti-diag loop question. This code was helpful to use in adapting to integer values (from strings/println's) and resulted in the following two methods. Note: the debug/system.out.println's are there for help/display.

    public static int getDiagonal(final List<List<Integer>> list, final int len) {
        int result = 0;
        // [top half]
        for (int i = len - 1; i > 0; --i) {
            //String temp = "";
            int tmp = 0;
            for (int j = 0, x = i; x <= len - 1; ++j, ++x) {
                final int val = list.get(x).get(j);
                //temp = temp + " " + val;
                tmp += val;
            }
            //System.out.println(temp);
            if (tmp > result)
                result = tmp;
        }
        // [lower half]
        for (int i = 0; i <= len - 1; ++i) {
            //String temp = "";
            int tmp = 0;
            for (int j = 0, y = i; y <= len - 1; ++j, ++y) {
                final int val = list.get(j).get(y);
                //temp = temp + " " + val;
                tmp += val;
            }
            //System.out.println(temp);
            if (tmp > result)
                result = tmp;
        }
        return result;
    }
    public static int getAntiDiagonal(final List<List<Integer>> list, final int len) {
        int result = 0;
        // [top half]
        for (int k = 0; k < len; ++k) {
            int tmp = 0;
            for (int j = 0; j <= k; ++j) {
                int i = k - j;
                int val = list.get(i).get(j);
                //System.out.print(val + " ");
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
            //System.out.println();
        }
        // [lower half]
        for (int k = len - 2; k >= 0; --k) {
            int tmp = 0;
            for (int j = 0; j <= k; ++j) {
                int i = k - j;
                int val = list.get(len - j - 1).get(len - i - 1);
                //System.out.print(val + " ");
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
            //System.out.println();
        }
        return result;
    }

Here's what the entire program ended up looking like to solve the original question:

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class App {
    public static void main(String[] args) {
        List<List<Integer>> data = readFile("C:\\Users\\Nick\\Desktop\\test.txt");
        for (List<Integer> row : data)
            System.out.println(row);
        final int n = data.size();
        int maxVertical = getVertical(data);
        int maxHorizontal = getHorizontal(data, n);
        int maxDiagonal = getDiagonal(data, n);
        int maxAntiDiagonal = getAntiDiagonal(data, n);
        System.out.println("max vertical = " + maxVertical);
        System.out.println("max horizontal = " + maxHorizontal);
        System.out.println("max diagonal = " + maxDiagonal);
        System.out.println("max anti-diagonal = " + maxAntiDiagonal);
    }
    public static int getVertical(final List<List<Integer>> list) {
        int result = 0;
        for (List<Integer> arr : list) {
            int curr = 0;
            for (Integer val : arr)
                curr += val;
            if (curr > result)
                result = curr;
        }
        return result;
    }
    public static int getHorizontal(final List<List<Integer>> list, final int len) {
        List<Integer> sums = new ArrayList<Integer>(list.get(0));
        for (int i = 1; i < len; ++i)
            for (int j = 0; j < len; ++j)
                sums.set(j, sums.get(j) + list.get(i).get(j));
        return Collections.max(sums);
    }
    public static int getDiagonal(final List<List<Integer>> list, final int len) {
        int result = 0;
        // [top half]
        for (int i = len - 1; i > 0; --i) {
            int tmp = 0;
            for (int j = 0, x = i; x <= len - 1; ++j, ++x) {
                final int val = list.get(x).get(j);
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
        }
        // [lower half]
        for (int i = 0; i <= len - 1; ++i) {
            int tmp = 0;
            for (int j = 0, y = i; y <= len - 1; ++j, ++y) {
                final int val = list.get(j).get(y);
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
        }
        return result;
    }
    public static int getAntiDiagonal(final List<List<Integer>> list, final int len) {
        int result = 0;
        // [top half]
        for (int k = 0; k < len; ++k) {
            int tmp = 0;
            for (int j = 0; j <= k; ++j) {
                int i = k - j;
                int val = list.get(i).get(j);
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
        }
        // [lower half]
        for (int k = len - 2; k >= 0; --k) {
            int tmp = 0;
            for (int j = 0; j <= k; ++j) {
                int i = k - j;
                int val = list.get(len - j - 1).get(len - i - 1);
                tmp += val;
            }
            if (tmp > result)
                result = tmp;
        }
        return result;
    }
    public static List<List<Integer>> readFile(final String path) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Path p = Paths.get(path);
        if (!Files.exists(p))
            return null;
        List<String> lines = null;
        try {
            lines = Files.readAllLines(p);
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (lines == null)
            return null;
        for (String str : lines) {
            List<Integer> row = new ArrayList<Integer>();
            final String line = str.substring(1, str.length() - 1);
            String[] arr = line.split(" ");
            for (String s : arr)
                row.add(Integer.valueOf(s.trim()));
            result.add(row);
        }
        return result;
    }
}

And finally, given the test.txt file contains:

|-2 5 3 2|
|9 -6 5 3|
|1 -8 2 -3|
|-1 2 -5 2|

Output result (should be) is:

[-2, 5, 3, 2]
[9, -6, 5, 3]
[1, -8, 2, -3]
[-1, 2, -5, 2]
max vertical = 11
max horizontal = 7
max diagonal = 7
max anti-diagonal = 14

Cheers

Edit I realized I didn't technically answer the original question completely so:

1. added these two lines to the very end of the main() method

   int result = maxVertical + maxHorizontal + maxDiagonal + maxAntiDiagonal; System.out.println("Result = " + result);

2. Add checks to each respective method (vert/horiz/diag/anti-diag) so that the case for the negative occurrence stated in problem

The largest (or maximal) sum of an array consisting of only negative integers is 0; that is, in that case we select the empty subarray

is able to be covered as well. This isn't a huge code overhaul persay, moreso a unique check.