[leetcode/lintcode 題解]算法面試真題詳解：内積

描述

給定長度為N的A數組，長度為K的B數組

你可以從A數組裡取K個數

規則如下：

• 每個Ai隻能被取出一次
• i==1ori==N 可以直接取出Ai
• 2≤i≤N−1 若Ai−1 或者 Ai+1 已經取出，則可以取出Ai

• 要取出正好K個數

  即每次可以從A數組的最左邊或者最右邊取走一個數，取走的數從數組中移除

  将取出的Ai按取出的順序 組成C數組

  求B與C的内積最大值

  B與C内積為∑i=0K−1Bi×Ci

  解釋1：

  A= [1,4,3,2,5]

  B=[1,2,3,4]

  K=4

  取出A0 ,C=[1]

  取出A4 C=[1,5]

  取出A1 C=[1,5,4]

  取出A2 C=[1,5,4,3]

  B·C=11+25+34+43=35

  這隻是C的一種可行方案，可能不是最優方案

  解釋2

  A=[1,2,3,4]

  不能直接取出A1 因為A0和A2都沒有取出

1≤K≤N≤2000

1≤Ai,Bi≤100000

線上評測位址：

領扣題庫官網

樣例
[2,3,5,1]
[2,1]
取出A0,A1           

算法DP

1. DP方程 dpijdpij表示從左邊取了i個數，從右邊取了j個數的最大内積
2. DP方程轉移

即判斷上一次從左邊取還是從右邊取數哪個内積更大

1. DP邊界條件 dp00=0dp00=0 兩邊都沒取數 内積為0
2. 答案 ans=max(ans,dpiK−i)ans=max(ans,dpiK−i) 即枚舉左邊取了多少個數，答案取dp數組最大值

   複雜度分析

   • 時間複雜度 n是A數組長度 K是B數組長度 左右兩邊取數均不超過K個 是以狀态量O(K2)O(K2) 轉移 O(1)O(1) 是以總時間複雜度O(K2)O(K2)
   • 空間複雜度 左右兩邊取數均不超過K個 是以狀态量O(K2)O(K2) 是以總空間複雜度O(K2)

public class Solution {
    /**
     * @param A: the A array
     * @param B: the B array
     * @return: return the maxium inner product of B and C
     */
    public long getMaxInnerProduct(int[] A, int[] B) {
        // write your code here
        //A數組長度
        int  n = A.length;
        //B數組長度
        int  K = B.length;
        //初始化dp數組
        //dp[i][j]表示從左邊取了i個數，從右邊取了j個數的最大内積
        long [][]dp = new long [K + 1][K + 1];

        //枚舉dp[i][j]
        for(int i = 0; i <= K; i++) {
            for(int j = 0; j <= K; j++) {

                //從左邊和右邊取數總數不超過K個
                if(i + j > K) {
                    break;
                }
                if(i + j > n) {
                    break;
                }
                //dp數組邊界條件，從左右都不取數的時候，dp[0][0]=0
                if(i == 0 && j == 0) {
                    dp[i][j] = 0;
                    continue;
                }

                //從左邊取的i 更新dp[i][j]
                if(i != 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + (long)A[i - 1] * (long)B[i + j - 1]);
                }
                //從右邊取的j，更新dp[i][j]
                if(j != 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - 1] + (long)A[n - j] * (long)B[i + j - 1]);
                }

            }
        }
        //枚舉從左邊取了多少，找最大的内積
        long ans = 0;
        for(int i = 0; i <= K; i++) {
            ans = Math.max(ans, dp[i][K - i]);
        }

        return ans;
    }
}           

更多題解參考： 九章官網solution