/**
* Get max sum from 2D array example
* Use Kadane's algorithm
* Maximum subarray problem: https://en.wikipedia.org/wiki/Maximum_subarray_problem
* Author: https://github.com/InterVi
*/
import java.lang.Math;
import java.util.AbstractMap.SimpleEntry;
import java.util.Map.Entry;

public class MaxSumExample {
  public static void main(String[] args) { //testing
    int[][] test = {
      {-1, -2, -1},
      {-20},
      {-40, -50},
      {-1, 2, 3, -4, 5},
      {4, -1, 2, 1},
      {1, 1, 20},
      {2, -4, -1},
      {1, 1}
    };
    System.out.print(maxSum2D(test));
  }

  /**
  * Kadane 1d
  * @return max sum
  */
  public static int maxSum(int[] a) {
    int result = a[0]; //get first value for correct comparison
    int sum = a[0];
    for (int i = 1; i < a.length; i++) {
      sum = Math.max(sum + a[i], a[i]); //first step getting max sum, temporary value
      result = Math.max(result, sum);
    }
    return result;
  }

  /**
  * Kadane 2d
  * @param array
  * @return max sum
  */
  public static int maxSum2D(int array[][]){
    int result = Integer.MIN_VALUE; //result max sum
    for (int i = 0; i < array.length; i++) {
      int sum = maxSum(array[i]);
      result = Math.max(result, sum);
    }
    return result;
  }
}