Facebook二面跪经。。。

zhenjieruan 发表于 2016-3-15 07:14
我理解0-x应该怎么做，但是x－size应该怎么做呢？是分治吗？

你设一个y,从x-size跑一遍，算出从x-y最大的n个连续数的和。然后让y从size-x倒着跑一遍算出y-size之间最大的n个连续数的和。然后再正向跑一遍得到y左边和右边加起来最大的和。总共跑了三遍。所以是o(n)

tk1322715 发表于 2016-3-15 07:31
你设一个y,从x-size跑一遍，算出从x-y最大的n个连续数的和。然后让y从size-x倒着跑一遍算出y-size之间最 ...

ok ok,让我想起了programming pearl里的一个算法，谢谢大神了！

tk1322715 发表于 2016-3-15 07:31
你设一个y,从x-size跑一遍，算出从x-y最大的n个连续数的和。然后让y从size-x倒着跑一遍算出y-size之间最 ...

Sorry,如果问题有点多。。这个x和y怎么选择？是选k吗？肯定得比k大吧

zhenjieruan 发表于 2016-3-15 07:36
Sorry,如果问题有点多。。这个x和y怎么选择？是选k吗？肯定得比k大吧

大概就是x从0到size, y就是从x到size. 真正写的话还有corner case，具体的值就得看你是怎么实现的了。

分享一个我的想法，用的是dp， 可以把3换成其他数字，时间复杂度 3*n，空间3*n，但是空间可以优化到n
    int maxSum(int[] array, int n) {
        int len = array.length;
        //sum[i] 是数组 array[i] 到 array[i+n-1] 的和
        int[] sum = new int[len - n + 1];
        int curSum = 0;
        for (int i = 0; i < len; i++) {
            if (i < n - 1) curSum += array[i];
            else {
                curSum += array[i];
                sum[i - n + 1] = curSum;
                curSum -= array[i - n + 1];
            }
        }
        int[][] dp = new int[3][sum.length];
        /*
         * dp[i][j] 的意思是，sum[j]之前的i个不overlap的n个array中连续数字的
         * 最大和＋sum[j]，所以basecase dp[0]就是sum数组本身
         */
        for (int i = 0; i < sum.length; i++) {
            dp[0][i] = sum[i];
        }
      
        for (int i = 1; i < 3; i++) {
            int curMax = 0;
            for (int j = 0; j < sum.length; j++) {
                if (j - i * n < 0) continue;
                curMax = curMax > dp[i-1][j - i * n] ? curMax : dp[i-1][j - i * n];
                dp[i][j] = curMax + sum[j];
            }
        }
        int max = 0;
        for (int j = 0; j < sum.length; j++) {
            max = max > dp[2][j] ? max : dp[2][j];
        }
        return max;
    }

代码写的匆忙可能有bug，欢迎大家讨论

這是我的想法，應該和他說的差不多吧@tk1322715， 簡單來說就是3個windows。我以中間的window為基準，往右滑動保持windows的合，然後，每次滑動，左右各用第一題的算法找出左邊最大以及右邊最大的windows合，3個相加后維護最大值，代碼如下：

1. import java.util.*;
   
2. public class Solution {
   
3.     public static void main(String[] args) {
   
4.         int[] nums = new int[]{1,3,7,7,2,1,1,4,8,8,6,1,1,9};
   
5.         System.out.println(maxThreeWindowSum(nums,2));
   
6.     }
   
7. 
   
8.     public static int maxWindowSum(int[] nums, int start, int end, int n) {
   
9.         if (nums == null || end - start+1 < n) throw new IllegalArgumentException();
   
10.         int sum = 0;
    
11.         int max = Integer.MIN_VALUE;
    
12.         Queue<Integer> window = new LinkedList<>();
    
13.         for (int i = start; i <= end ; i++) {
    
14.             if(window.size() < n-1) {
    
15.                 sum+=nums[i];
    
16.                 window.offer(nums[i]);
    
17.             } else {
    
18.                 sum+=nums[i];
    
19.                 window.offer(nums[i]);
    
20.                 max = Math.max(max,sum);
    
21.                 sum-=window.poll();
    
22.             }
    
23.         }
    
24.         return max;
    
25.     }
    
26. 
    
27.     public static int maxThreeWindowSum(int[] nums, int n) {
    
28.         if (nums == null || nums.length < 3*n) throw new IllegalArgumentException();
    
29.         //move the window in the middle and find max window at both side;
    
30.         int max = Integer.MIN_VALUE;
    
31.         int middle = 0;
    
32.         Queue<Integer> window = new LinkedList<>();
    
33.         for (int i = n; i < nums.length-2*n; i++) {
    
34. 
    
35.             if(window.size() < n-1) {
    
36.                 middle+=nums[i];
    
37.                 window.offer(nums[i]);
    
38.             } else {
    
39.                 middle+=nums[i];
    
40.                 window.offer(nums[i]);
    
41.                 int left = maxWindowSum(nums, 0, i-n, n);
    
42.                 int right = maxWindowSum(nums, i+1, nums.length -1, n);
    
43.                 max = Math.max(max, left + middle + right);
    
44.                 middle-=window.poll();
    
45.             }
    
46.         }
    
47.         return max;
    
48.     }
    
49. }

复制代码

补充内容 (2016-3-15 08:29):
時間應該是O(n^2)

补充内容 (2016-3-15 08:36):
33筆誤，應為i < nums.length -n;

novice00 发表于 2016-3-15 07:42
分享一个我的想法，用的是dp， 可以把3换成其他数字，时间复杂度 3*n，空间3*n，但是空间可以优化到n
     ...

层主看了你的答案。我感觉可能有点不对的地方。
curMax = curMax > dp[i-1][j - i * n] ? curMax : dp[i-1][j - i * n];
dp[i][j] = curMax + sum[j];
这两行代买我有点疑惑。
根据你的定义，dp[i-1][j - i * n] =sum[j - i * n]之前的i个不overlap的n个array中连续数字的最大和 + sum(j - i*n);
那这个sum(j- i * n) 所代表的连续n个数可能和后面的sum(j)重合。然后你之后dp[i][j]又加一次sum[j]。我感觉就有可能加错了。

guschen802 发表于 2016-3-15 08:28
這是我的想法，應該和他說的差不多吧@tk1322715， 簡單來說就是3個windows。我以中間的window為基準，往右 ...

厉害厉害。哈哈，感觉这道题能有leetcode的hard里偏简单的。而且实现起来可能还有很多小技巧。不然的话代码可能会很乱。

tk1322715 发表于 2016-3-15 08:40
厉害厉害。哈哈，感觉这道题能有leetcode的hard里偏简单的。而且实现起来可能还有很多小技巧。不然的话代 ...

我覺得還能再優化，每次左右都有重複的搜索，如果能保存歷史的話，例如左邊，每多一個數字，組成一個新的window,和歷史最大比就好，不用從頭開始掃..不過想想就覺得有點複雜

guschen802 发表于 2016-3-15 09:00
我覺得還能再優化，每次左右都有重複的搜索，如果能保存歷史的話，例如左邊，每多一個數字，組成一個新的 ...

请问你的代码第41行，求i左边的maxWindowSum为什么不是i-1而是i-n？