摘要:
Problem
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).Solution
class Solution { public int[] maxSumOfThreeSubarrays(int[] nums, int k) { //three parts: 0 ~ i-1, i ~ i+k-1, i+k ~ n-1 (i >= k) // (n-1) - (i+k) + 1 >= k ... so (i <= n-2k) if (nums == null || nums.length < 3*k) return null; int n = nums.length; int[] sum = new int[n+1]; int[] left = new int[n]; int[] right = new int[n]; int[] res = new int[3]; int max = 0; for (int i = 0; i < n; i++) { sum[i+1] = sum[i] + nums[i]; } int leftMax = sum[k]-sum[0]; left[k-1] = 0; for (int i = k; i < n; i++) { if (sum[i+1]-sum[i+1-k] > leftMax) { left[i] = i+1-k; leftMax = sum[i+1]-sum[i+1-k]; } else { left[i] = left[i-1]; } } int rightMax = sum[n]-sum[n-k]; right[n-k] = n-k; for (int i = n-1-k; i >= 0; i--) { if (sum[i+k]-sum[i] > rightMax) { right[i] = i; rightMax = sum[i+k]-sum[i]; } else { right[i] = right[i+1]; } } for (int i = k; i <= n-2*k; i++) { int l = left[i-1]; int r = right[i+k]; int curMax = sum[l+k]-sum[l] + (sum[i+k]-sum[i]) + (sum[r+k]-sum[r]); if (curMax > max) { max = curMax; res[0] = l; res[1] = i; res[2] = r; } } return res; } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/71850.html
Problem Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. Note:You may assume the intervals end point is alway...
摘要:前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫~現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...
摘要:自己沒事刷的一些的題目,若有更好的解法,希望能夠一起探討項目地址 自己沒事刷的一些LeetCode的題目,若有更好的解法,希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...
Problem Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isnt one, return 0 instead. Note The sum of the entire nums array is guaranteed to fit ...
摘要:復雜度思路對于每一節點,考慮到這一個節點為止,所能形成的最大值。,是經過這個節點為止的能形成的最大值的一條支路。 Leetcode[124] Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. For this problem, a path is defined as any se...
閱讀 1718·2021-10-18 13:34
閱讀 3906·2021-09-08 10:42
閱讀 1551·2021-09-02 09:56
閱讀 1606·2019-08-30 15:54
閱讀 3127·2019-08-29 18:44
閱讀 3298·2019-08-26 18:37
閱讀 2212·2019-08-26 12:13
閱讀 453·2019-08-26 10:20