Java solution with explanation, using kadanes


#1

Need to know:

  1. kadanes

  2. max sum sub matrix
    My improvised method, using max sum sub matrix logic (which uses kadanes)
    Given the unique circumstance that each value is greater than
    previous row and column value
    we need to find max sub matrix from A[rows-1][cols-1]
    therefore, instead of starting from each column and calculating prefix sum array from there till end cols
    we calculate prefix sum array starting from col = cols-1 only and for each prefix sum array apply kadanes

    public class Solution {
     public int kadanes(int[] arr) {
         int max=arr[0];
         int runSum=arr[0];
         
         for (int i=1;i<arr.length;i++) {
             runSum+=arr[i];
             runSum=Math.max(runSum,arr[i]);
             
             if(runSum>max) {
                 max=runSum;
             }
         }
         
         return max;
     }
     
     public int solve(int[][] A) {
         int rows=A.length;
         int cols=A[0].length;
         int max=Integer.MIN_VALUE;
       
         int[] temp = new int[rows];
         for (int j=cols-1;j>=0;j--) {
             
             for (int i=0;i<rows;i++) {
                 temp[i] += A[i][j];
             }
             
             int val = kadanes(temp);
             max = Math.max(val,max);
         }
         
         return max;
     }
    

    }