1) Given an array containing positive and negative integers, how would you find the sub-array with maximum sum. In other words, given A[1..n] how would you find A[j..k] such that A[j] + ... + A[k] is maximum.

package personal.puzzles;

public class LargestSumSubarray {
    
    public static Pair getLargestSumSubarray(int[] array) {
        int finalLeft = 0;
        int finalRight = 0;
        int left = 0;
        int right = 0;
        int sum = Integer.MIN_VALUE;
        int runningSum = 0;
        while (right < array.length) {
            runningSum += array[right];
            if (runningSum >= sum) {
                sum = runningSum;
                finalLeft = left;
                finalRight = right;
            }
            if (runningSum < 0) {
                runningSum = 0;
                left = right + 1;
            }
            right++;
        }
        return new Pair(finalLeft, finalRight);
        
    }
    
    public static void main(String[] args) {
        int array[] = {-11, -2, -3, -8, 6, -22};
        Pair idx = LargestSumSubarray.getLargestSumSubarray(array);
        System.out.println(idx.getX() + "  " + idx.getY());
    }
    
    
    private static class Pair {
        private int x;
        private int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public int getX() {
            return x;
        }
        public int getY() {
            return y;
        }
    }
}