📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3478| 回复: 15
跳转到指定楼层
上一主题 下一主题
收起左侧

求问snapchat常问的一道题

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
求问一道snapchat常考的一道dp题目:给个一个数组[1,1,2,1],然后用+ * ()三操作求出这个数组的最大值,这个题返回6。还是没搞明白这题代码如何写。有没有地里大神指导一下

上一篇:NQueens I II
下一篇:大家来一起讨论一下4sum的o(n^2)的解法吧

本帖被以下淘专辑推荐:

全局:
如果允许负数,只存max应该不行吧,万一两个比较小的负数,一乘变大了呢?我测试了下{-1, -3, -3, -1}结果不对。我把所有结果都保存下来了,这个测试通过了。
class Solution2 {
    public int getmax(int[] nums) {
            List<List<Integer>> res = new LinkedList<>();
            List l1 = new LinkedList<>(), l2 = new LinkedList<>();
            l1.add(nums[0]);
            res.add(l1);
            l2.add(nums[0]+nums[1]);
            l2.add(nums[0]*nums[1]);
            res.add(l2);
            for (int i = 2; i < nums.length; i++) {
                    List<Integer> tmp = new LinkedList<>();
                    for (int x: res.get(i-1)) {
                            tmp.add(x+nums[i]);
                            tmp.add(x*nums[i]);
                    }
                    int tmpp = nums[i]+nums[i-1];
                    for (int x: res.get(i-2)) {
                            tmp.add(x*tmpp);
                    }
                    res.add(tmp);
            }
            int max = Integer.MIN_VALUE;
            for (int x: res.get(nums.length-1)) {
                    if (x > max) {
                            max = x;
                    }
            }
            return max;
    }
}

评分

参与人数 1大米 +10 收起 理由
asiawildboar + 10 手动给我何神点赞^_^

查看全部评分

回复

使用道具 举报

推荐
hj867955629 2015-9-10 11:52:13 | 只看该作者
全局:
sorry, 少考虑了一种情况。

class Solution4 {
    public int getmax(int[] nums) {
            List<List<Integer>> res = new LinkedList<>();
            List l1 = new LinkedList<>(), l2 = new LinkedList<>();
            l1.add(nums[0]);
            res.add(l1);
            l2.add(nums[0]+nums[1]);
            l2.add(nums[0]*nums[1]);
            res.add(l2);
            for (int i = 2; i < nums.length; i++) {
                    List<Integer> tmp = new LinkedList<>();
                    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
                    for (int x: res.get(i-1)) {
                            int x1 = x+nums[i], x2 = x*nums[i];
                            max = Math.max(max, Math.max(x1, x2));
                            min = Math.min(min, Math.min(x1, x2));
                    }
                    int tmpp = nums[i]+nums[i-1];
                    for (int x: res.get(i-2)) {
                            int xx = x*tmpp;
                            max = Math.max(max, xx);
                            min = Math.min(min, xx);
                    }
                    tmpp = nums[i]*nums[i-1];
                    for (int x: res.get(i-2)) {
                            int xx = x+tmpp;
                            max = Math.max(max, xx);
                            min = Math.min(min, xx);
                    }
                    tmp.add(max);
                    tmp.add(min);
                    res.add(tmp);
            }
            return res.get(nums.length-1).get(0);
    }
}
回复

使用道具 举报

推荐
pyemma 2015-9-7 12:25:36 | 只看该作者
全局:
  1. import java.util.*;

  2. /**
  3.   Description: give an array, use +, * and () to obtain the maximum result
  4.   Example: [1,1,2,1] => 6
  5.   Solution: dp[i][j][k], maximum value from i to j using + (k = 0) or * (k = 1)
  6. */
  7. public class MaxExpression {
  8.         public static int maxExpression (int[] nums) {
  9.                 if (nums.length == 0) return 0;
  10.                 else if (nums.length == 1) return nums[0];

  11.                 int n = nums.length;
  12.                 int[][] dp = new int[n][n];
  13.                 for (int len = 0; len < n; ++len) {
  14.                         for (int i = 0; i < n - len; ++i) {
  15.                                 int j = i + len;
  16.                                 if (len == 0) {
  17.                                         dp[i][j] = nums[i];
  18.                                         continue;
  19.                                 }
  20.                                 for (int k = i; k < j; ++k) {
  21.                                         dp[i][j] = Math.max(dp[i][j],
  22.                                                 dp[i][k] + dp[k+1][j]);
  23.                                         dp[i][j] = Math.max(dp[i][j],
  24.                                                 dp[i][k] * dp[k+1][j]);
  25.                                 }
  26.                         }
  27.                 }
  28.                 return dp[0][n-1];
  29.         }

  30.         public static void main(String[] args) {
  31.                 int[] a = new int[]{1, 1, 2, 1};
  32.                 System.out.println(maxExpression(a));
  33.         }
  34. }
复制代码
Dp problem, dp[i][j] record the max value from position i to j. This dp is in the from of bottom to top.
回复

使用道具 举报

🔗
AndyLiu0429 2015-9-7 11:18:10 | 只看该作者
全局:
  1. public class Solution {
  2.    
  3.     public static int max(int[] nums) {
  4.         int n = nums.length;
  5.         int[][] dp = new int[n][n];

  6.         for (int i = 0; i < n; i++) {
  7.             dp[i][i] = nums[i];
  8.         }

  9.         for (int l = 2; l <= n; l++) {
  10.             for (int i = 0; i <= n - l; i++) {
  11.                 int j = i + l - 1;
  12.                 int max = Integer.MIN_VALUE;

  13.                 for (int k = i; k < j; k++) {
  14.                     int tmp = Math.max(dp[i][k] * dp[k + 1][j],
  15.                             dp[i][k] + dp[k + 1][j]);
  16.                     max = Math.max(tmp, max);
  17.                 }
  18.                 dp[i][j] = max;
  19.             }
  20.         }

  21.         return dp[0][n - 1];
  22.     }

  23.     public static void main(String[] args) {
  24.         assert max(new int[] {1, 1, 2, 1}) == 6;
  25.     }
  26. }
复制代码
看一下对不对。dp[i][j] 代表从i到j的最大值。

评分

参与人数 2大米 +8 收起 理由
krist + 3 感谢分享!
爱丽丝和鲍勃 + 5

查看全部评分

回复

使用道具 举报

🔗
hj867955629 2015-9-8 05:46:38 | 只看该作者
全局:
话说snapchat不是e verify?那还有投的必要吗。。。。
回复

使用道具 举报

🔗
pyemma 2015-9-8 07:01:40 | 只看该作者
全局:
hj867955629 发表于 2015-9-7 13:43
如果允许负数,只存max应该不行吧,万一两个比较小的负数,一乘变大了呢?我测试了下{-1, -3, -3, -1}结果 ...

In this case, use an additional dimension to hold the result for * and + separately.
回复

使用道具 举报

🔗
AndyLiu0429 2015-9-8 09:22:43 | 只看该作者
全局:
hj867955629 发表于 2015-9-8 05:43
如果允许负数,只存max应该不行吧,万一两个比较小的负数,一乘变大了呢?我测试了下{-1, -3, -3, -1}结果 ...

这个是指数级复杂度吧。。如果有负数的话,再存一个dp表示i到j的最小值就好了,然后状态转移方程类似maximum product array。。
回复

使用道具 举报

🔗
pyemma 2015-9-8 11:59:19 | 只看该作者
全局:
AndyLiu0429 发表于 2015-9-7 17:22
这个是指数级复杂度吧。。如果有负数的话,再存一个dp表示i到j的最小值就好了,然后状态转移方程类似maxi ...

是的,存储一个最大和最小
回复

使用道具 举报

🔗
hj867955629 2015-9-9 01:24:37 | 只看该作者
全局:
AndyLiu0429 发表于 2015-9-8 09:22
这个是指数级复杂度吧。。如果有负数的话,再存一个dp表示i到j的最小值就好了,然后状态转移方程类似maxi ...

嗯,follow up一下就好了
回复

使用道具 举报

🔗
readman 2015-9-9 02:24:24 | 只看该作者
全局:
...**小声问一句.
如果都是整数, 为什么还要dp....greedy不可以么...看到1就加,看到其他的就乘?  x*y >= x+y | x,y >1 ?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表