<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return the maximum sum of a <strong>non-empty</strong> subsequence of that array such that for every two <strong>consecutive</strong> integers in the subsequence, <code>nums[i]</code> and <code>nums[j]</code>, where <code>i &lt; j</code>, the condition <code>j - i &lt;= k</code> is satisfied.</p>

<p>A <em>subsequence</em> of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,2,-10,5,20], k = 2
<strong>Output:</strong> 37
<b>Explanation:</b> The subsequence is [10, 2, 5, 20].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,-2,-3], k = 1
<strong>Output:</strong> -1
<b>Explanation:</b> The subsequence must be non-empty, so we choose the largest number.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [10,-2,-10,-5,20], k = 2
<strong>Output:</strong> 23
<b>Explanation:</b> The subsequence is [10, -2, -5, 20].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        heap = [(0, -1)]
        res = float('-inf')

        for i, v in enumerate(nums):
            # print(i, v)
            # print(heap)
            # if v >= 0:
            #     allnegative = False
            while heap and heap[0][1] < i - k:
                heapq.heappop(heap)

            # only v itself, or concatenate with previous result
            resi = max(v, v - heap[0][0])
            res = max(resi, res)
            heapq.heappush(heap, (-resi, i))
        
        return res

    def constrainedSubsetSum_(self, nums: List[int], k: int) -> int:
        # We can find all the positive pionts first, and then try to connect the points with negative points
        # One key fact is that, for the final sub sesequnce
        # 1. both ends are positive
        # 2. any positive points in between will be included (easy to prove with contradiction)

        # so we can compute the best resut ending at each positive position, and extend the result to the right 
        # positive points. 
        pos = [i for i, v in enumerate(nums) if v > 0]
        if len(pos) < 2:
            return max(nums)

        
        # find the possible next connecting points after i
        # not all points need to check: if a point is at right and bigger, all points on the left with smaller value 
        # should be pruned. We can use a mono stack to get those points.
        # Smaller points on the right need to consider since it is on the right and give possibility to connect 
        # righter points which could be bigger.
        def nextPoints(i, r):
            stack = []
            for j in range(i+1, min(i+k+1, r)):
                while stack and nums[j] >= nums[stack[-1]]:
                    stack.pop()
                stack.append(j)
            # print(i, stack)
            return stack

        def maxconnects(i, j):
            # find the maximum sum of connecting points between i, j
            # using dijsktra algorithm
            # same cost we choose the right most position
            q = [(0, -i)]
            cost = [float('inf')] * (j-i)
            while q:
                c, p = heapq.heappop(q)
                p *= -1
                if p + k >= j:
                    return -c
                if cost[p-i] <= c:
                    continue
                else:
                    cost[p-i] = c
                    for np in nextPoints(p, j):
                        if c - nums[np] < cost[np-i]:
                            heapq.heappush(q, (c-nums[np], -np))
            return float('-inf')                

        res = nums[pos[0]]
        pre = res
        pp = pos[0]
        print(pos)
        for i in range(1, len(pos)):
            p = pos[i]
            pv = nums[p]
            if p - pp <= k:
                pre += pv
            else:
                # find points to connect p, pp
                c = maxconnects(pp, p)
                pre = max(pre+c+pv, pv)
            
            res = max(res, pre)
            pp = p
        return res
            
36900