LintCode 43 [最大サブアレイIII]
Lintcode 43
元の質問
説明
整数の配列と数kが与えられた場合、合計が最大の重複しないサブ配列をk個見つけます。
各サブアレイの番号は連続している必要があります。
最大の合計を返します。
整数の配列と整数kが与えられた場合、それらの合計が最大になるように、重複しないk個のサブ配列を見つけます。
配列内の各サブ配列の数は連続している必要があります。
最大の合計を返します。
例
Input: List = [-1,4,-2,3,-2,3] k = 2 Output: 8 Explanation: 4 + (3 + -2 + 3) = 8 Give the array [-1,4,-2,3,-2,3], request to split into 2 groups The maximum output is: 8 Reason: divided into two groups [4] [3, -2, 3] => 4 + (3 + -2 + 3) = 8 思想
これは、動的計画法の非常に古典的なトピックです。主なソリューションは「ローカル最適ソリューションとグローバル最適ソリューション」と呼ばれます。基本的な考え方はこれです。各ステップで、2つの変数を維持します。1つは現在の要素の最適解であるグローバル最適であり、もう1つはローカル最適です。つまり、現在の要素の最適解が含まれている必要があります。
localMax[n][k]局所最適が定義され、最初のn個の数について、k番目のグループにn番目の要素が含まれている必要があることを示します。
globalMax[n][k]グローバル最適化が定義され、最初のn個の数値について、kグループにn番目の要素が含まれていない可能性があることを示します。
localMax[n][k]更新の過程で、n番目の番号を含める必要があるため、次の2つのことが起こります。
1. n番目の要素はグループです。つまり、最初のn-1個の数値がk-1個のグループに分割され、現在のグローバル最適解globalMax[n-1][k-1]
2. n番目の要素は他の要素と一緒にk個のグループに分割されます。つまり、他のn-1個の要素はすでにkグループを構成しており、添え字の添え字の位置は連続しているため、（n-1）番目の要素はkに表示される必要がありますグループ、現在の局所最適解localMax[n-1][k]
-再帰式localMax[n][k] = max(globalMax[n-1][k-1], local[n-1][k]) + the nth element
globalMax[n][k]更新の過程で、n番目の数が不確実であるかどうかにかかわらず、2つのケースがあります。
1. n番目の要素は含まれていません。つまり、他のn-1要素はkグループを形成する必要があり、グローバルな最適解はglobalMax[n-1][k]です。
2. n番目の要素が含まれます。これは、n個の要素がkグループを形成し、現在の局所最適解localMax[n][k]を意味します。
-再帰式globalMax[n][k] = max(globalMax[n-1][k], local[n][k])
完全なコード
public class Solution { /** * @param nums: A list of integers * @param k: An integer denote to find k non-overlapping subarrays * @return: An integer denote the sum of max k non-overlapping subarrays */ public int maxSubArray(int[] nums, int k) { // write your code here if (nums == null || nums.length == 0) { return 0 } int len = nums.length int[][] localMax = new int[len + 1][k + 1] int[][] globalMax = new int[len + 1][k + 1] for (int i = 1 i <= len i++) { for (int j = 1 j <= i && j <= k j++) { localMax[j - 1][j] = Integer.MIN_VALUE globalMax[j - 1][j] = Integer.MIN_VALUE localMax[i][j] = Math.max(localMax[i - 1][j], globalMax[i - 1][j - 1]) + nums[i - 1] globalMax[i][j] = Math.max(localMax[i][j], globalMax[i - 1][j]) } } return globalMax[len][k] } }