Algorithm筆記 10.2 - greedy演算法練習: 最大化dot-product

如果你也在修Coursera Algorithm Toolbox的話，這是解答！請斟酌使用

問題定義

給兩個整數vector v1 = {a1,a2, ... , an} , v2 = {b1, b2, ... , bn}，找出最大的dot product?

按照greedy algorithm步驟，我們要先找一個safe move，並且證明其為某個optimal solution的第一步。依照題目，我們假設“v1和v2從大到小排序後所得的dot product為optimal”。

證明safe move

假設一optimal solution w = {a1*b1 + a2*b2 +.. + aj*bj + .... + ak*bk + ....  + an*bn}，且ak = max(a1, a2,..,an), bj = max(b1, b2, ...,bn)。

如果w' = 把w中的 aj*bj 和 ak*bk 交換成 ak*bj和 aj*bk，則w' - w = ak*bj+aj*bk - aj*bj - ak*bk = ak*(bj-bk) + aj*(bk-bj) = (ak-aj)*(bj-bk) > 0，因為ak 和 bj分別是兩個數列中的最大值。

演算法

注意要integer相乘可能會oveflow，先cast成為long

private static long maxDotProduct(int[] a, int[] b) {
    Integer[] A = new Integer[a.length];
    Integer[] B = new Integer[a.length];

    //O(n)    
    for (int i = 0; i < a.length; i++) {
        A[i] = a[i];
        B[i] = b[i];
    }

    //O(nlogn)    
    Arrays.sort(A, new Comparator<Integer>() {
        @Override        
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    //O(nlogn)    
    Arrays.sort(B, new Comparator<Integer>() {
        @Override        
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    //O(n)    
    long result = 0;
    for (int i = 0; i < a.length; i++) {
        result += (long)A[i] * (long)B[i];
    }

    return result;


}