拆分数组使和最大从递归到迭代

algorithm

---

拆分数组

• 拆分数组，题目大意，给定一个数组$A$，和数组长度$K$，最多可以把一个数组拆分成长度为$K$的子数组（连续）。并且拆分后把子数组的值，替换为这个子数组内最大的值。可能存在多个这样的数组，求拆分多个数组后的变化和最大。例如$A = [1,15,7,9,2,5,10], K = 3$，拆分结果为$[15,15,15,9,10,10,10]$时，子数组的和才是最大的。
• 理解这个题目之后，可以看出这个题目是类似于整数分割。在某个位置进行分割，求得一次分割的结果后，再继续求解下次的分割，两次分割是同一个问题的不同规模。

---

方法一：递归

• 直观想法，求解的是$A[1,n]$可以拆分的最大结果。我们可以假设第一次拆分是在$i$处，即$A[1,i]$是一个拆分结果，计算出这次拆分出来的子数组的和。那么第二次拆分就是从$A[i+1,n]$。很显然这个可以用递归的方法来解决。求解完$A[i+1,n]$之后和$A[0,i]$的结果合并。获取最大的拆分结果。
• 假设$f[i]$表示的是从$A[i,n]$的拆分结果最大值，那么完整的数组$A$被拆分的结果为，$maxsum[1,i] + f[i+1]$
• 可以认为，我们每次解决一个问题，然后递归求解剩余的问题。剩下的问题$A[i+1,n]$实际上是一个规模更小的问题。
• 递归基本情况是：A[i,n]只有一个或者0个元素，那么返回0或者元素本身。
• 其实我们只分析了内容但是并不知道i的取值是多少，实际上我们从0开始可以得到$i \in [1,K]$

$$f[i] = maxsum_{j=i}^{i+K}{A[i,j]} + f[j+1]$$

• 最后的结果是$f[0]$。
• 讨论递归出口
• 1 $i>=n$

    int sum = INT_MIN;
    int maxSumAfterPartitioning(vector<int>& A, int K)
    {
        return maxsum(A,0,K);
        // maxsum(A, 0, K);
        // return sum;
    }
    int maxsum(vector<int>& A, int i, int K)
    {
        int n = A.size();
        if (i >= n)
            return 0;
        int s = 0;
        for (int k = 0; k < K; k++) {
            int j = i + k;
            if (j >= n)
                break;
            int maxe = maxElem(A, i, j);
            int size = k + 1;
            int sumk = maxe * size;
            s = max(s, sumk + maxsum(A, j + 1, K));
            // sum = max(sum, s); global max result
        }
        return s;
    }
    int maxElem(vector<int>& A, int i, int j)
    {
        int c = A[i];
        for (int k = i + 1; k <= j; ++k) {
            c = max(c, A[k]);
        }
        return c;
    }

• 时间复杂度:$T(n) =O(2^n)$。
• 空间复杂度:函数调用
• 其中求解$A[i,j]$的最大元素可以优化，可知$j \in [0,K-1]$。每次迭代计算$k=0\cdots K-1$时，数组$A[i,j]$最大值可额外保存。参见方法三。

---

方法二：转化为备忘录递归

• 上述方式存在子问题重复计算的情况，例如计算$f[0]$,需要计算 $f[1] , f[2]$,$f[K] \cdots$,计算$f[2]$时，需要计算，$f[3] \cdots f[4]$,$f[K] \cdots$，,可以发现非常多的子问题需要重新计算，我们用map，也可以用数组，来缓存已经计算完的数据。对于已经获取的数据直接返回结果。
• 对于已经计算出来的符号排列结果用map来保存，例如map[2]=x，表示$A[i,n]$的子数组分割的最大值。

    int sum = INT_MIN;
    unordered_map<int, int> umap;
    int maxSumAfterPartitioning(vector<int>& A, int K)
    {
        maxsum(A, 0, K);
        return sum;
    }
    int maxsum(vector<int>& A, int i, int K)
    {
        int n = A.size();
        if (i >= n)
            return 0;
        if (umap.find(i) != umap.end())
            return umap[i];
        int s = 0;
        for (int k = 0; k < K; k++) {
            int j = i + k;
            if (j >= n)
                break;
            int maxe = maxElem(A, i, j);
            int size = k + 1;
            int sumk = maxe * size;
            s = max(s, sumk + maxsum(A, j + 1, K));
            sum = max(sum, s);
        }
        umap[i] = s;
        return s;
    }
    int maxElem(vector<int>& A, int i, int j)
    {
        int c = A[i];
        for (int k = i + 1; k <= j; ++k) {
            c = max(c, A[k]);
        }
        return c;
    }

• 时间复杂度：$T(n) = O(nk^2)$，子问题个数为$O(nk)$。TODO
• 空间复杂度：$O(n)$，需要使用哈希表，存储子问题的结果。
• 其中求解$A[i,j]$的最大元素可以优化，可知$j \in [0,K-1]$。每次迭代计算$k=0\cdots K-1$时，数组$A[i,j]$最大值可额外保存。参见方法三。

---

方法三：拆分数组（转化为迭代计算）

• 从第二步，能看出，我们可以从基本情况（小规模的问题），来推导更为大的规模。
• 假设$f[i]$ 表示$A[0,i]$拆分的最大值。那么新加入一个数$A[i+1]$，$f[i+1]$便可以有规模更小的情况求出来。
• 也可以把$f[n]$作为基本情况，开始计算，直到$f[0]$计算出来，两者本质并无差别。

$$f[i] = max_{j=i-1}^{i-K} \{f[j] + max(A[j+1,i])*k\}$$
- 基本情况：$f[i] = A[i],k=1$

    int maxSumAfterPartitioning(vector<int>& A, int K)
    {
        int n = A.size();
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            int maxe = 0;
            for (int k = 0; k < K; ++k) {
                int j = i - k;
                if (j < 0)
                    break;
                int dpj = 0;
                if (j >= 1)
                    dpj = dp[j - 1];
                maxe = max(maxe, A[j]);
                int dpjsum = maxe * (k + 1);
                dp[i] = max(dpj + dpjsum, dp[i]);
            }
        }
        return dp[n - 1];
    }

• 时间复杂度:$O(n)$,空间复杂度：$O(n)$
• 这里求解$A[i,j]$的最大值的过程可以其实在从$A[i,i+k]$的遍历过程中是能够保存的。