SnapChat电面

给定数组，只有正数，使用＋和＊和（）。求最大值。

使用DP解

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

n], dp[0][m] + dp[m][len]), m = 0...len.

hno3 发表于 2015-3-12 13:24
谢谢回复，感觉清楚多了

补充内容 (2015-3-12 13:28):

当i大于等于4时候，一定可以将这些数分为两个集合，每个集合有多于等于2个数，也就保证每个集合最大值肯定大于1。而如果两个大于1的集合，一定是乘才会得到最大值。

一维DP就够了吧

1.       
   
2.         int[] k = new int[A.length];
   
3.         k[0] = A[0];
   
4.         
   
5.         for (int i = 1; i < A.length; i++) {
   
6.             k[i] = Math.max(k[i - 1] * A[i], (i >= 2 ? k[i - 2] : 1) * (A[i - 1] + A[i]));
   
7. 
   
8.             if (i - 2 >= 0) {
   
9.                 k[i] = Math.max(k[i], (i >= 3 ? k[i - 3] : 1) * (A[i - 2] + A[i - 1] + A[i]));
   
10.             }
    
11.         }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

楼主这里dp[m][j]是什么东西啊 没看明白，能解释下么

请问 dp 是一维数组么？  dp[m][j] 是什么？
max() 是调用的递归函数么？
不明觉厉

whuwangyi 发表于 2015-2-4 15:26
我电面也是这一道题目，是一个ABC出的么？

LZ的DP看得不太明白，我的做法是O(N^3)复杂度，很好奇O(N^2) ...

你过了么？

tangtianlei 发表于 2015-2-4 06:40
楼主这里dp[m][j]是什么东西啊 没看明白，能解释下么

抱歉，写错了     

qjx026 发表于 2015-2-4 08:31
请问 dp 是一维数组么？  dp[m][j] 是什么？
max() 是调用的递归函数么？
不明觉厉

不是递归，使用dp循环