动态规划2：计算最大连续子序列和

import java.util.HashMap;
import java.util.Map;

public class DynamicProgramming2 {
    public static void main(String[] args) {
        int[] arr = {3,-4,2,-1,2,6,-5,4};
        //暴力枚举法
        System.out.println(getMaxSumSubArr(arr));
        //加上记忆Map
        System.out.println(getMaxSumSubArr2(arr));
        //从后往前，不用递归
        System.out.println(getMaxSumSubArr3(arr));
    }

    /**
     * 求其中和最大的连续子序列
     * 暴力枚举法
     * @param arr
     * @return
     */
    public static int getMaxSumSubArr(int[] arr){
        int sum = arr[0];
        for (int i = 0; i < arr.length; i++) {
            //每轮循环算出从index=i开头的和最大的子序列
            int tmp = getMaxSumSubArrGivingStartIndex(arr,i);
            sum = tmp>sum?tmp:sum;
        }
        return sum;
    }

    public static int getMaxSumSubArrGivingStartIndex(int[] arr, int startIndex) {
        if (startIndex == arr.length-1){
            //如果是最后一个序号，那肯定就是它自己了
            return arr[arr.length-1];
        }

        //子序列的最大和无非就是当前元素加上后续序列的和，但如果后续序列和小于0，那说明不加更大
        int maxSumSubArrGivingStartIndex = getMaxSumSubArrGivingStartIndex(arr, startIndex + 1);
        return arr[startIndex] + (maxSumSubArrGivingStartIndex >0?maxSumSubArrGivingStartIndex:0);
    }

    /**
     * 求其中和最大的连续子序列
     * 加上记忆Map
     * @param arr
     * @return
     */
    public static int getMaxSumSubArr2(int[] arr){

        Map<Integer,Integer> memo = new HashMap<>();

        int sum = arr[0];
        for (int i = 0; i < arr.length; i++) {
            //每轮循环算出从index=i开头的和最大的子序列
            //返回的结果中subArr[0]为最大和，subArr[1]为对应的子序列
            int tmp = getMaxSumSubArrGivingStartIndex(arr,i);
            sum = tmp>sum?tmp:sum;
        }
        return sum;
    }

    public static int getMaxSumSubArrGivingStartIndex2(int[] arr, int startIndex,Map<Integer,Integer> memo) {
        if (memo.get(startIndex) != null) {
            return memo.get(startIndex);
        }

        if (startIndex == arr.length-1){
            memo.put(startIndex,arr[arr.length-1]);
            return arr[arr.length-1];
        }

        int maxSumSubArrGivingStartIndex = getMaxSumSubArrGivingStartIndex(arr, startIndex + 1);
        int result = arr[startIndex] + (maxSumSubArrGivingStartIndex > 0 ? maxSumSubArrGivingStartIndex : 0);

        memo.put(startIndex,result);
        return result;
    }

    /**
     * 求其中和最大的连续子序列
     * 取消递归
     * @param arr
     * @return
     */
    public static int getMaxSumSubArr3(int[] arr){

        Map<Integer,Integer> memo = new HashMap<>();

        for (int i = arr.length-1; i >= 0 ; i--) {
            //从后往前，每轮循环算出从序号i开始的最大连续和
            if (i == arr.length-1){
                memo.put(i,arr[i]);
                continue; //注意这里是continue不是break
            }

            Integer tmp = memo.get(i + 1);
            int sum = tmp >0?arr[i]+tmp:arr[i];
            memo.put(i,sum);
        }

        int maxSum = memo.get(arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            Integer tmp = memo.get(i);
            maxSum = tmp>maxSum?tmp:maxSum;
        }

        return maxSum;
    }
}