package misc;

public class MaximalSubarray {

private static int[] arr = {1, -2, 3, 4, -9, 6};

private int getMaxSubSum(int[] arr) {

int maxSum = 0;

int partialSum = 0;

for(int i = 0; i < arr.length; i++) {

partialSum += arr[i];

maxSum = Math.max(maxSum, partialSum);

if(partialSum < 0) {

partialSum = 0; // Zero if negative

}

}

return maxSum;

}

public static void main(String[] args) {

MaximalSubarray obj = new MaximalSubarray();

int sum = obj.getMaxSubSum(arr);

System.out.println("Sum: "+sum); // 3 + 4 = 7

}

}