美文网首页
689. Maximum Sum of 3 Non-Overla

689. Maximum Sum of 3 Non-Overla

作者: Jeanz | 来源:发表于2018-03-13 03:03 被阅读0次

    In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum.

    Each subarray will be of size k, and we want to maximize the sum of all 3*k entries.

    Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

    Example:

    Input: [1,2,1,2,6,7,5,1], 2
    Output: [0, 3, 5]
    Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
    We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.
    

    Note:

    • nums.length will be between 1 and 20000.
    • nums[i] will be between 1 and 65535.
    • k will be between 1 and floor(nums.length / 3).

    首先用sliding window, 存下window下的sum.

    然后类似于左右范围内的比较的问题,我们有一个left array和一个right array, 来存从左到右,left[i],到达i这个window的最大值。从右到左,right[i],到达i这个window的最大值
    然后重新扫描这些window, (表示第三个的位置),找到sum最大的地方。

    class Solution {
        public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
            int sum = 0, len = nums.length - k + 1;
            int[] sums = new int[len];
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                if (i >= k) sum -= nums[i - k];
                if (i >= k - 1) sums[i - k + 1] = sum;
            }
            
            int[] left = new int[len];
            int best = 0;
            for (int i = 0; i < len; i++) {
                if (sums[i] > sums[best]) best = i;
                left[i] = best;
            }
            
            int[] right = new int[len];
            best = len - 1;
            for (int i = len - 1; i >= 0; i--) {
                if (sums[i] >= sums[best]) best = i;
                right[i] = best;
            }
            
            int[] res = {0, k, 2 * k};
            for (int j = k; j < len - k; j++) {
                int i = left[j - k], z = right[j + k];
                if (sums[i] + sums[j] + sums[z] > sums[res[0]] + sums[res[1]] + 
    sums[res[2]]) {
                    res[0] = i;
                    res[1] = j;
                    res[2] = z;
                }
            }
            return res;
        }
    }
    

    相关文章

      网友评论

          本文标题:689. Maximum Sum of 3 Non-Overla

          本文链接:https://www.haomeiwen.com/subject/radafftx.html