[LeetCode] 689. 3つの重複しないサブアレイの最大合計問題解決レポート(Python)



689 Maximum Sum 3 Non Overlapping Subarrays Problem Solving Report



著者:Xue MingZhuネガティブ
id:fuxuemingzhu
個人ブログ: http://fuxuemingzhu.cn/


トピックアドレス: https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/



トピックの説明:

与えられた配列でnums正の整数の場合、合計が最大の重複しない3つのサブ配列を見つけます。

各サブ配列のサイズはkであり、すべての3*kの合計を最大化する必要があります。エントリ。



結果を、各間隔の開始位置を表すインデックスのリストとして返します(0-インデックス付き)。複数の回答がある場合は、辞書式順序で最小のものを返します。

例:

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.

注意:



  1. nums.lengthは1から20000の間です。
  2. nums [i]は1から65535の間になります。
  3. kは1からfloor(nums.length / 3)の間になります。

局所

非常に長い配列を重複しない3つのサブ配列に分割します。各サブ配列の長さはkであり、最終的な目的は3つのサブ配列の合計である必要があります。

問題解決方法

トピックのデータを見て、O(N)ソリューションが必要であることを確認してください。さらに、最も価値のある問題の最適化は一般にDPです。どうやるか?

3つの配列を、左、中央、および右の配列と考えてください。中間配列の位置を指定した後、位置の左側と右側で最大と最大のサブ配列を見つけ、3つの配列を追加して最大の合計を取得します。

sums配列を使用して、累積合計を各場所に保存します。これの利点は、2つの場所からサブアレイの合計を直接減算できることです。さらに、左右に2つのDPアレイが必要です。

Left [i]は、長さkの開始位置と、範囲[0、i]内の最大のサブアレイを示します。

Right [i]は、長さkの開始位置と、範囲[i、n-1]内の最大のサブアレイを示します。

左の方法は左から右にトラバースされ、右のメソッドは右から左にトラバースされます。サブ配列の長さは最初のK位置でk未満であるため、左の値は0であり、右の値はN-kであり、これはサブインターバルのエッジの場合のインデックスを表します。更新プロセスは難しくありません。既存のサブアレイを最大化して比較してから、インデックス位置を更新することです。

各位置の左右にある長さkのサブ配列を見つけたら、中央の配列であるウィンドウを使用して配列を再度トラバースする必要があります。これが最大の配列になり、中間配列の位置を決定する場合は左右で問題になります。すでに左右がわかっているので、テーブルを調べて位置を確認するのと同じです。

この質問は、合計にヘッダー0を追加します。これの利点は、これまでの合計を取得するときに、numの0番目の配列から直接前の合計+現在の数値を見つけることができることです。

この質問の最も難しい部分は、圧倒的なインデックス値であるはずです...とにかく、私は気を失いました。

時間計算量はO(N)であり、空間計算量はO(N)です。

class Solution(object): def maxSumOfThreeSubarrays(self, nums, k): ''' :type nums: List[int] :type k: int :rtype: List[int] ''' N = len(nums) sums = [0] left = [0] * N right = [N - k] * N mx = 0 res = [0, 0, 0] for i, num in enumerate(nums): sums.append(sums[-1] + num) total = sums[k] - sums[0] for i in range(k, N): if sums[i + 1] - sums[i - k + 1] > total: left[i] = i - k + 1 total = sums[i + 1] - sums[i - k + 1] else: left[i] = left[i - 1] total = sums[N] - sums[N - k] for j in range(N - k - 1, -1, -1): if sums[j + k] - sums[j] >= total: right[j] = j total = sums[j + k] - sums[j] else: right[j] = right[j + 1] for i in range(k, N - 2 * k + 1): l, r = left[i - 1], right[i + k] total = (sums[i + k] - sums[i]) + (sums[l + k] - sums[l]) + (sums[r + k] - sums[r]) if total > mx: mx = max(mx, total) res = [l, i, r] return res

参考資料:

https://www.cnblogs.com/grandyang/p/8453386.html

日付

2018年10月5日-休日は終わりました! !