Leetcode題解 Python & C#：Constrained Subset Sum

給一串整數陣列，回傳最大非空子集合的最大總和，子集合為連續的 nums[i] nums[j] 組成，j<i 且 j-i <= k。

本來今天高高興興的，結果這一題沒有在時限內完成。光是看懂題目就已經用上三十分鐘。

等到明暸的時候，也無啥時間可寫了。檢討失敗的原因，我想是對這樣的題型陌生吧。

由於是集合，所以可選相同位置上的(如前一組的j，後一組的i)，但每一個位置只會被計算到一次。

因此如果使用深度優先的遞迴函數，我倒是沒寫好在取相同位置的判斷。(我就在這裡卡住)

這顕是DP的題型，因此選擇會紀錄什麼是接下來首先思考的。

如果遞迴函數不適合，那可以攤開變成迴圈，並且由後往前找。

由於一次選擇一定要成對nums[i] nums[j]，因此從 len(nums) - 2 之處開始。(-1位置是無法選一對的)

接者，在 [i+1,i+k] 的範圍中選擇最大的總和，所以DP是紀錄該位置上的總和，然後nums[i] + max([i+1:i+k+1])為dp[i]新的總和。


例題與流程：
[1,-1,1,2,3], 2
[1,-1,1,5,3]
[1,-1,6,5,3]
[1,5,6,5,3]
[7,5,6,5,3]
=> max() => 7

[-1,-2,-3],1
[-1,-2,-3]
[-1,-2,-3]
=> max() => -1

由於 k 可能會很大，如果都跑完一定會超時。但其實在選擇最大值的時候，就已經決定了題目中的子集合的最後一個元素。

如果迴圈[i+1,i+k]超越上次最大值所選的位置，後面也不會有更大的總和，所以當前位置就可以不用再往下選最大總和與自身相加。

去掉不必要的部分，這樣就能加快速度，順利完成此題。

Python

class Solution:
    def constrainedSubsetSum(self, nums, k):
        maxIndex = len(nums)
        for i in range(maxIndex-2, -1, -1):           
            value = nums[i]          
            for j in range(1,min(k+1,maxIndex-i)):
                if value + max(0, nums[i+j]) > nums[i]:
                    nums[i] = value + max(0, nums[i+j])
                    maxIndex = i+j+1
        return max(nums)

C#

public class Solution {
    public int ConstrainedSubsetSum(int[] nums, int k) {
        int maxIndex = nums.Length;
        for(int i = nums.Length-2; i >= 0; i--)
        {
            int v = nums[i];
            int ik = (k+1 < maxIndex-i)? k+1: maxIndex-i;
            for(int j = 1; j < ik; j++)
            {
                int num = v + (nums[i+j] <= 0? 0: nums[i+j]);
                if( num > nums[i])
                {
                    nums[i] = num;
                    maxIndex = i+j+1;  
                }
                
            }
        }
        return nums.Max();
    }
}