package prac;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
從[0]開始
每次都有至多六種選擇
最後抵達[n-1]
目的: sum是最大的

(DP)
重點一: 用一個陣列紀錄每次六個選項中的最佳結果
重點二: 概念上是將每次開頭都當成一個新的子集合，之前的資訊即為確認資訊。程式跑的邏輯像是
(1) 從第0個(i)開始，向前移動六次(j)(因為是第一輪，所以沒有前一個最佳結果可參考)
(2) 再來，從第1個(i)開始，向前移動六次(j)。
    每次比較 "上一輪的最佳結果bestResult[j]" vs "這一輪的起始值bestResult[i]+當下這格的值Ary[j]"。
    取較大者
(3) 循環下去
(4) 何時結束: 當i與j都碰到Ary[j]
 * @author sam
 *
 */
public class NumberSolitaire{
    public static int SUBARRAY_MINIMUM_LENGTH = 2;
    public static void main(String a[]){

        int [] ary = {1, -2, 0, 9, -1, -2}; // 五個 - ans: 8
//        int [] ary = {1, -2, -3, -4, -1, -7, -9, -10}; // 八個 - ans: -10
        int solution = solution(ary);
        System.out.println("solution: " + solution);
    }

    /**
     * TIME(O): (n-1) + (n-1)/2 + (n-1)/3 + (n-1)/4 + ..... + (n-1)/(n-1) ->  / 1*2*3*....*(n-1)
     * SPACE(O): N
     * @param A
     * @return
     */
    private static int solution(int A[])
    {
        // N //  N is an integer within the range [2..100,000];
        // A[] // each element of array A is an integer within the range [−10,000..10,000].
        int N = A.length;
        int[] bestResult = new int[N]; // 紀錄目前最佳結果
        Arrays.fill(bestResult, Integer.MIN_VALUE); // 塞入最小值

        // 初始值
        bestResult[0] = A[0];
        for (int i = 0;i < A.length;i++) {
//          System.out.printf(" index: %d %n", i);
            // 下六個這狀況把它記起來
            for (int j = i + 1; (j < A.length) && (i < A.length) && j < (i + 1) + 6; j++) {
                // 比較 之前最高 與 加上A[j] 誰大誰小
                int preMaxResult = bestResult[j]; // 暫存目前最大可能數
                int nowMaxResult = bestResult[i] + A[j]; // 前一步驟(i)最大可能數 + 現在數值A[j]
                bestResult[j] = Math.max(preMaxResult, nowMaxResult);
//              System.out.printf("(i,j)=(%d,%d) 上一個最大結果: %11d or 加上當下的結果: %4d -> 較大結果: %4d ###### %n", i, j, preMaxResult , bestResult[i] + A[j], bestResult[j]);
            }
        }
        // {1, -2, -3, -4, -1, -7, -9, -10}

        return bestResult[bestResult.length-1];
    }
}