package com.smart.algorithm.str;

/**
 * 最大子序列和 的四种算法
 * Created by fc.w on 2018/05/08
 */
public class MaxSubSum {

    public static void main(String[] args) {
        int[] arr= {3, 4, 5, 2, 3, 1, 2, 1, 8, 4, 1, 9};
        System.out.println("穷举法:      " + maxSubSum1(arr));
        System.out.println("穷举法改进： " + maxSubSum2(arr));
        System.out.println("分治策略:    " + maxSubSum3(arr, 0 , arr.length - 1));
        System.out.println("效率最高，代码最简单: " + maxSubSum4(arr));
    }

    /**
     * 穷举法；
     * 算法思想：算出每个子序列的和，即算出序列中第i个到第j个数的和(j>=i)，并进行比较
     * 最笨的方法，分别以每个元素为起点 计算每一种长度的和
     * 时间复杂度O(N^3)
     * @param arr
     * @return
     */
    public static int maxSubSum1(int[] arr) {
        int maxSum = arr[0];
        int sum = arr[0];

        for (int i = 0; i < arr.length; i++) { // 每一个元素为起点
            for (int j = i; j < arr.length; j++) { // 每一种子序列长度
                sum = arr[i];
                for (int k = i + 1; k <= j; k++) { // 求和
                    sum += arr[k]; // 计算arr[i] 和 arr[j]之和
                }
                if (sum > maxSum) {
                    maxSum = sum;
                }
            }
        }

        return maxSum;
    }

    /**
     * 穷举法的改进，通过一个for循环直接得出 某个元素为起点的所有子序列的最大和
     * 算法思想：第一个算法的第三个for循环中有大量不必要的重复计算，
     * 如：计算i到j的和，然而i到j-1的和在前一次的循环中已经计算过，无需重复计算，故该for循环可以去掉
     * 
     * 运行时间为O(N^2)
     * @param arr
     * @return
     */
    public static int maxSubSum2(int[] arr) {
        int sum = 0;
        int maxSum = arr[0];
        for (int i = 0; i < arr.length; i++) {
            sum = 0;
            for (int j = i; j < arr.length; j++) {
                sum += arr[j];
                if (sum > maxSum) {
                    maxSum = sum;
                }
            }
        }

        return maxSum;
    }

    /**
     * 分治策略
     * 算法思想：把问题分成两个大致相等的子问题，然后递归地对它们求解，这是“分”的部分。
     * “治”阶段将两个子问题的解修补到一起并可能再做些少量的附加工作，最后得到整个问题的解。
     *
     * 在该问题中，如果把序列从中间分为两部分，那么最大子序列和可能在三处出现：
     * 1. 整个出现在输入数据的左半部，
     * 2. 整个出现在右半部，
     * 3. 跨越分界线。
     * 前两种情况可以递归求解，第三种情况的最大和可以通过
     * 求出前半部分（包括前半部分的最后一个元素）的最大和
     * 以及后半部分（包含后半部分的第一个元素）的最大和而得到，此时将两个和相加。
     *
     * 1. 每次把数组分成左右两部分，
     * 2. 最大子序列和可能在三处出现，整个序列出现在左边或者右边，或者跨越中部
     *
     * 运行时间 O(N*logN)
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int maxSubSum3(int[] arr, int left, int right) {
        // 基本情况，left=right，只有一个元素
        if (left == right)
            return arr[left];

        int center = (left + right) / 2; // 递归，继续分成左右两部分，
        int maxLeftSum = maxSubSum3(arr, left, center); // 返回左边的最大和
        int maxRightSum = maxSubSum3(arr, center + 1, right); // 返回右边的最大和

        /* 计算从center为起点，分别向左和向右的最大序列和  */
        // 1. center向左的最大子序列和
        int maxLeftBorderSum = arr[center];
        int leftBorderSum = arr[center];
        for (int i = center - 1; i >= left; i--) {
            leftBorderSum += arr[i];
            if (leftBorderSum > maxLeftBorderSum) {
                maxLeftBorderSum=leftBorderSum;
            }
        }

        // 2. center向右的最大子序列和
        int maxRightBorderSum = arr[center + 1];
        int rightBorderSum = arr[center + 1];
        for (int j = center + 2; j <= right; j++) {
            rightBorderSum += arr[j];
            if (rightBorderSum > maxRightBorderSum) {
                maxRightBorderSum = rightBorderSum;
            }
        }

        // 3. 返回三种情况的最大值（整个在左边，整个在右边，跨区域）
        int max;
        max = maxLeftSum > maxRightSum ? maxLeftSum : maxRightSum;
        max = max > leftBorderSum + rightBorderSum ? max : leftBorderSum + rightBorderSum;

        return max;
    }

    /**
     * 效率最高，代码最简单
     * 思路：小于0的子序列（包括单个元素的情况）比较sumMax后直接抛弃，sum重置为0，继续累加
     *
     * 运行时间：O(N)
     * @param arr
     * @return
     */
    public static int maxSubSum4(int[] arr) {
        int sum = arr[0];
        int maxSum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            sum += arr[i];
            if (sum > maxSum) {
                maxSum = sum;
            }
            if (sum < 0) {
                sum = 0;
            }
        }

        return maxSum;
    }

}