maxsubarray.java

import java.util.Arrays;
import java.util.Random;

public class MaxSubArray {
    public static int maxSubArray(int[] arr) {
        if (arr.length == 0) {
            return 0;
        }
        int maxEndingHere = arr[0];
        int maxSoFar = arr[0];
        for (int i = 1; i < arr.length; i++) {
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

    public static class Pair<T, T1> {
        public T1 first;
        public T1 second;

        public Pair() {

        }

        public Pair(Pair<T1, T1> currentPair) {
            this.first = currentPair.first;
            this.second = currentPair.second;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "first=" + first +
                    ", second=" + second +
                    '}';
        }
    }


    public static int maxSubSum(int[] houses) {
        if (houses.length == 0) {
            return 0;
        }
        Integer sum = 0;
        Integer maxSum = 0;
        Pair<Integer, Integer> bestPair = new Pair<>();
        Pair<Integer, Integer> currentPair = new Pair<>();
        currentPair.first = 0;
        currentPair.second = 0;

        bestPair.first = 0;
        bestPair.second = 0;
        for (int i = 0; i < houses.length; ++i) {
            sum = sum + houses[i];
            currentPair.second = i;
            if (sum > maxSum) {
                bestPair = new Pair<>(currentPair);
                maxSum = sum;
            }
            if (sum < 0) {
                sum = 0;
                currentPair.first = i + 1;
            }
        }
//        System.out.println(bestPair);
        int result = 0;

        for (int i = bestPair.first; i <= bestPair.second; i++) {
            result += houses[i];
        }
        return result;
    }

    public static int my(int[] arr) {
        if (arr.length == 0) {
            return 0;
        }
        int sum = arr[0];
        int maxSum = arr[0];
        int maxSumIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            sum += arr[i];
            if (sum > maxSum) {
                maxSum = sum;
                maxSumIndex = i;
            }
        }

        sum = 0;
        int maxSum2 = arr[maxSumIndex];
        int maxSumIndex2 = maxSumIndex;
        for (int i = maxSumIndex; i >=0; i--) {
            sum += arr[i];
            if (sum > maxSum2) {
                maxSum2 = sum;
                maxSumIndex2 = i;
            }
        }

        int result = 0;
        System.out.println(maxSumIndex2 + ", " + maxSumIndex);
        for (int i = maxSumIndex2; i <= maxSumIndex; i++) {
            result += arr[i];
        }
        return result;
    }

    public static Random r = new Random();

    public static int[] gen() {
        int len = r.nextInt(20);
        int[] result = new int[len];
        for (int i = 0; i < result.length; i++) {
            result[i] = r.nextInt(200) - 100;
        }
        for (int i = 0; i < result.length; i++) {
            if (result[i] > 0) {
                return result;
            }
        }
        return gen();
    }

    public static void main(String[] args) {
        // 4 -1 2 1
        // 3 - 6
//        int[] arr = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
//        System.out.println(maxSubArray(arr));
//        System.out.println(maxSubSum(arr));

        for (int i = 0; i < 10000000; i++) {
            int[] arr = gen();
            if (maxSubArray(arr) != my(arr)) {
                System.out.println(Arrays.toString(arr));
                System.out.println(maxSubArray(arr));
                System.out.println(my(arr));
                break;
            }
        }
//        int[] arr = new int[] { -13, -66, -3 };
//        System.out.println(maxSubArray(arr));
//        System.out.println(maxSubSum(arr));
    }
}