gistfile1.txt

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var maxSumAfterPartitioning = function(arr, k) {
    // [10,9,3,2]
    // k = 2
    // 30
    // [[10], [9, 3], [2]]
    
    // k = 2
    // [10,9,3,2] = [[10], [9, 3], [2]]
    // [10,9,3,10] = [[10, 9], [3, 10]]
    const dp = {};
    const dpm = {};
    const sub = (s, e) => {
        if (s >= e) return 0;
        const dpi = s*1000+e;
        const res = dp[dpi];
        if (!!res) return res;
        const maxArr = (ss,ee) => {
            const r = dpm[ss*1000+ee];
            if (!!r) return r;
            let max = 0, maxI = 0;
            for(let i=ss;i<ee;i++) {
                if (max < arr[i]) {
                    max = arr[i];
                    maxI = i;
                }
            }
            return dpm[ss*1000+ee] = {max,maxI};
        };
        if (e - s <= k) {
            dp[dpi] = maxArr(s,e).max*(e-s);
            return dp[dpi];
        }
        const maxI = maxArr(s,e).maxI;
        //. 1 2 3 4 5 6 7 8 9 0 1
        // [1,4,1,5,7,3,6,1,9,9,3]
        let max = 0;
        for(let kkk = k; kkk > 0; kkk--) {
            for(let kk = maxI - kkk + 1; kk <= maxI; kk++) {
                if (kk < 0) continue;
                const li = Math.max(s,kk);
                const ri = Math.min(e,kk+kkk);
                const left = sub(s, li);
                const mid = sub(li,ri);
                const right = sub(ri,e);
                const v = left + mid + right;
                if (v > max) max = v;
            }
        }
        dp[dpi] = max;
        return max;
    }
    return sub(0, arr.length);
};