Envío 6247

Código

import java.util.HashMap;
import java.util.Objects;
import java.util.Scanner;

public class Main {
    private static HashMap <String, Integer> memoizationPartialSumColumns = new HashMap<>();
    private static HashMap <String, Integer> memoizationMaxSubarray = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int r = scanner.nextInt();
        int c = scanner.nextInt();

        int[][] matrix = new int[r][c];
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                matrix[i][j]=scanner.nextInt();
            }
        }

        //O(r^2) * O(c) = O(r^2 * c)
        for (int column=0; column<c; column++) {
            //O(r) * O(r) = O(r^2)
            for (int j = 0; j < r; j++) {
                partialSumsColumn(0, j, column, matrix); //Recursive Method -> O(r)
            }
        }


        int max = Integer.MIN_VALUE;
        //O(r * c) * O(r) = O(r^2 * c)
        for(int startRow=0; startRow<r; startRow++) {
            //O(c) * O(r) = O(r * c)
            for (int endRow = startRow; endRow <r; endRow++) {
                for(int startColumn = 0; startColumn<c; startColumn++) { //O(c) when recursive method takes O(1), O(1) in the other cases
                    int localMax = maxSubarray(startRow, endRow, startColumn, c - 1); //Recursive Method -> O(c)
                    if (localMax > max) {
                        max = localMax;
                    }
                }
            }
        }

        System.out.println(max);
    }


    private static int partialSumsColumn(int start, int end, int column, int[][]matrix){
        String key = new Key(start, end, column).toString();
        if(memoizationPartialSumColumns.containsKey(key)){
            return memoizationPartialSumColumns.get(key);
        }

        if(start == end){
            memoizationPartialSumColumns.put(key, matrix[start][column]);
            return matrix[start][column];
        }

        int recResponse = partialSumsColumn(start+1, end, column, matrix);
        int value = matrix[start][column];

        memoizationPartialSumColumns.put(key, recResponse+value);
        return recResponse + value;
    }


    private static int maxSubarray(int rowStart, int endRow, int startColumn, int endColumn){
        String partialSumsKey = new Key(rowStart, endRow, startColumn).toString();
        String maxSubarrayKey = new Key(rowStart, endRow, startColumn).toString();

        if(memoizationMaxSubarray.containsKey(maxSubarrayKey)){
            return memoizationMaxSubarray.get(maxSubarrayKey);
        }

        if(startColumn==endColumn){
            memoizationMaxSubarray.put(maxSubarrayKey, memoizationPartialSumColumns.get(partialSumsKey));
            return memoizationPartialSumColumns.get(partialSumsKey);
        }

        int valueStart = memoizationPartialSumColumns.get(partialSumsKey);
        int recResponse = maxSubarray(rowStart, endRow, startColumn+1, endColumn); //O(r)

        int max = Math.max(valueStart, valueStart+recResponse);

        memoizationMaxSubarray.put(maxSubarrayKey, max);
        return max;
    }


    private static class Key{
        private int start;
        private int end;
        private int column;

        public Key(int start, int end, int column) {
            this.start = start;
            this.end = end;
            this.column = column;
        }

        @Override
        public String toString() {
            return "Key{" +
                    "start=" + start +
                    ", end=" + end +
                    ", column=" + column +
                    '}';
        }

        @Override
        public int hashCode() {
            return Objects.hash(start, end, column);
        }
    }
}