一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1263|回复: 15
收起左侧

[算法题] 求问snapchat常问的一道题

[复制链接] |试试Instant~ |关注本帖
f1371342385 发表于 2015-9-7 09:11:17 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

本帖被以下淘专辑推荐:

hj867955629 发表于 2015-9-8 05:43:59 | 显示全部楼层
如果允许负数,只存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

查看全部评分

回复 支持 1 反对 0

使用道具 举报

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[j] 代表从i到j的最大值。

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

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[j] record the max value from position i to j. This dp is in the from of bottom to top.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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 ?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-9 04:27:24 | 显示全部楼层
readman 发表于 2015-9-9 02:24
...**小声问一句.
如果都是整数, 为什么还要dp....greedy不可以么...看到1就加,看到其他的就乘?  x*y >= x ...

[1,1,2,1],你的意思是(1+1)*2+1=5, 但是(1+1)*(2+1)=6更大。
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-9 05:06:37 | 显示全部楼层
hj867955629 发表于 2015-9-9 04:27
[1,1,2,1],你的意思是(1+1)*2+1=5, 但是(1+1)*(2+1)=6更大。

sort一下呢...
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-10 06:14:33 | 显示全部楼层

sort一下原来不沾边的两个数在一起了,这样不符合题意吧。
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-9-10 11:34:35 | 显示全部楼层
只存最大最小值

class Solution {
    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);
                    }
                    tmp.add(max);
                    tmp.add(min);
                    res.add(tmp);
            }
            return res.get(nums.length-1).get(0);
    }
}
回复 支持 反对

使用道具 举报

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);
    }
}
回复 支持 反对

使用道具 举报

shindave 发表于 2015-10-3 06:27:31 | 显示全部楼层
分享一段递归解的代码(只支持数组里有正数):
  1. public class Solution {

  2.         public static void main (String [] args){
  3.         Solution client = new Solution();
  4.         int [] nums = {1, 1, 2, 1};
  5.         System.out.println(client.maxResult(nums));
  6.         }

  7.     public int maxResult(int [] nums) {
  8.         return recMax(nums, 0, nums.length-1);
  9.     }

  10.     public int recMax(int [] nums, int start, int end) {
  11.         if (start == end)
  12.             return nums[start];
  13.         if (start+1 == end) {
  14.             return Math.max(nums[start]+nums[end], nums[start]*nums[end]);
  15.         }
  16.         int max = 0;
  17.         for (int k = start; k < end; k++) {
  18.             int left = recMax(nums, start, k);
  19.             int right = recMax(nums, k+1, end);
  20.             int tempmax = Math.max(left+right, left*right);
  21.             max = Math.max(max, tempmax);
  22.         }
  23.         return max;
  24.     }
  25. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 01:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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