[leetcode/lintcode 题解]算法面试真题详解:内积-阿里云开发者社区

开发者社区> 算法编程> 正文
登录阅读全文

[leetcode/lintcode 题解]算法面试真题详解:内积

简介: [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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接