Maximum Alternating Subsequence Sum - Dynamic Programming - Leetcode 1911 - Python

0:00 - Read the problem
1:37 - Drawing Explanation
6:50 - Coding Explanation

leetcode 1911

#dynamic #programming #subsequence
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[Caucasian_Shepherd]

Nice. There is even an easier solution. In every iteration we need to compare three things (there are three candidates for max sum):
1. Previous max sum
2. Number at the current index
3. Previous max sum + current number - previous number. That is, if we want to add a new number in our subsequence, we have to add the previous number as well to keep the current number at an even position. Otherwise, it will be subtracted from the alternating sum.

The pseudocode of this algorithm is given below:

sum = nums[0];
for (i = 0; i < nums.length; i++)
sum = max(sum, nums[i], sum - nums[i - 1] + nums[i]);
return sum;

[pramodhjajala]

Learning with you has always been fun and exciting to me . Thanks a lot and please keep going . You are helping lot of people

[mykytapiskarov]

@NeetCode you explain it easier and more clear than top rated solutions at Leetcode!

[VarunMittal-viralmutant]

I think returning sumEven works only b'coz nums are positive integers. Correct me if I am wrong

If someone is confused, like I was ;), about:
tmpEven = max(sumOdd + nums[i], sumEven)

Think of it this way :
tmpEven should always reflect the max subsequence if the index ending at that element is even.
And what options do we have if nums[i] is the last even index:
* Either add it to the subsequence ---> sumOdd + nums[i]
* Skip including it coz the odd indexed num is too big with a -ve sign ---> sumEven

Hence tmpEven = max(sumOdd + nums[i], sumEven)

[dc]

Instead of computing maimum with labels, i compute maximum and minimum with label "even"
class Solution:
def maxAlternatingSum(self, nums: List[int]) -> int:
prior_max = 0
prior_min = 0
for n in nums:
temp = prior_max
if (prior_max < n - prior_min):
prior_max = n - prior_min
if (prior_min > n - temp):
prior_min = n - temp
return prior_max

[TheElementFive]

A couple of questions I have about this problem:

(1) what do the instructions mean by “reindexing”
(2) How come in the third example the problem provides we are adding 5 if its index (5) is an odd number??

[minguero]

can we say that creating decision tree is part of dfs? I'm just wondering because it feels like we are defining the edges and trying to find the edge that contains max value.

[VarunMittal-viralmutant]

Alternate code for the recursive solution. Without the cache it hits TLE
Inbuilt cache can be simply replaced with dp[(num, sign)]

def max_alternating_sum(nums):

@cache
def _max_sum(i, sign):
if i == len(nums):
return 0

incd = nums[i] * sign + _max_sum(i+1, sign*(-1))
not_incd = _max_sum(i+1, sign)

return max(incd, not_incd)

return _max_sum(0, 1)

[abhishekbirhade]

@Neetcode could you say that the recursive solution is greedy ? I think yes because at each step you are picking the max at each node in the decision tree.

[nurulafsar]

The bottom up DP solution I believe doesn’t need to be reversed. In fact it seems it’s marginally faster actually if you don’t do that

[sidazhong]

Why do we need a tmpeven and tmpodd variable? And why it has to be reversed?

[chiraagpala]

Why does the thumbnail of this video have the company logo's? How do you know if new problems on leetcode are used if it isnt on the premium lists?

[chandragupta]

when you added -5, how the path is a subsequence, its subset

[sarveshmaurya]

can anyone please tell me, how the dp solution is O(N) time ...
According to me it should be O(N^2) as we are generating all the subsequences🙄😕

[jonaskhanwald]

do this problem from today's contest:
Count Ways to Build Rooms in an Ant Colony

[bismeetsingh]

I can only understand the memoized N^2 solution, passes on leetcode though.