Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * 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;
- }
- }
Add Comment
Please, Sign In to add comment