package chap04_Divide_And_Conquer;

import static org.junit.Assert.*;

import java.util.Arrays;

import org.junit.Test;

/**
 * 算反导论第四章 4.1 最大子数组
 * 
 * @author xiaojintao
 * 
 */
public class Maximum_Subarray_Problem {
    /**
     * 最大子数组类 left为头部索引，right为尾部索引，sum为数组和
     * 
     * @author xiaojintao
     * 
     */
    protected static class MaxSubarray {
        int left;
        int right;
        long sum;

        public MaxSubarray(int left, int right, long sum) {
            this.left = left;
            this.right = right;
            this.sum = sum;
        }
    }

/**
     * 类似减治法，更快速的球最大子数组，支持全部都是负数的数组
     * 
     * @param n
     * @return
     */
    static MaxSubarray findMaxSubarrayFaster(int[] n) {
        long sum = Long.MIN_VALUE;
        int right = 0;
        int left = 0;
        int negativeCounter = 0;
        long tempSum = Long.MIN_VALUE;
        long tempSum1 = 0;
        // 考虑全是负数
        for (int i = 0; i < n.length; i++) {
            if (n[i] < 0) {
                if (tempSum < n[i]) {
                    tempSum = n[i];
                    right = i;
                }
                negativeCounter += 1;
            } else if (n[i] >= 0) {
                left = i;
                break;
            }
        }
        if (negativeCounter == n.length) {
            left = right;
            return new MaxSubarray(left, right, tempSum);
        } else {
            for (int j = left; j < n.length; j++) {
                tempSum1 += n[j];
                if (tempSum1 > sum) {
                    sum = tempSum1;
                    right = j;
                }
            }
            sum = Long.MIN_VALUE;
            tempSum1 = 0;
            int tempLeft = left;
            for (int k = right; k >= tempLeft; k--) {
                tempSum1 += n[k];
                if (tempSum1 > sum) {
                    sum = tempSum1;
                    left = k;
                }
            }
            return new MaxSubarray(left, right, sum);
        }

    }

    /**
     * 更快的打印最大子数组
     * 
     * @param n
     */
    static void printMaxSubarrayFaster(int[] n) {
        MaxSubarray maxSubarray = findMaxSubarrayFaster(n);
        int[] result = Arrays.copyOfRange(n, maxSubarray.left,
                maxSubarray.right + 1);
        System.out.println("MaxSubarray is " + Arrays.toString(result) + "from"
                + maxSubarray.left + " to " + maxSubarray.right + ", Sum is "
                + maxSubarray.sum);
    }
}