📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: f1371342385
跳转到指定楼层
上一主题 下一主题
收起左侧

求问snapchat常问的一道题

🔗
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. }
复制代码
回复

使用道具 举报

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

本版积分规则

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