#🔒 dp algos question

5 messages · Page 1 of 1 (latest)

worthy veldt
#

you have an array A with non negative integers. if A[i] = 0, then remove the 0 and exactly one of its neighbors. return the maximum sum of the array after all 0's have been removed and the indices of the elements not removed

i'm not exactly sure how to recover the indices of the elements left after all 0s have been removed. i think i've solved the maximum sum part, looks something like this. my thought is that dp[i] represents the maximum sum after removing up to index i.

I also do some preprocessing so that even length sequences of consecutive 0s are removed and odd length sequences of consecutive 0s are replaced by only one 0. There's also a small edge case where A starts with a 0 but i've handled that separately.

how would i recover the indices of the elements that haven't been removed?

n = len(A)
dp = [0]*n
dp[0] = A[0]
dp[1] = A[1] + A[0] if 0 not in [A[0], A[1]] else 0

for i in range(2, n):
  if A[i] == 0:
    dp[i] = dp[i-2]
  elif A[i-1] == 0:
    dp[i] = max(dp[i-2], A[i]+dp[i-1])
  else:
    dp[i] = dp[i-1] + A[i]

return dp[-1]
full compassBOT
#

@worthy veldt

Python help channel opened

Remember to:

  • Ask your Python question, not if you can ask or if there's an expert who can help.
  • Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
  • Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.
median light
#

Maybe make a secondary array like:

ary2 = list(enumerate(A))

That makes a list with each entry a 2-tuple of (i,v) where i is the index and v is the value from A.

Do all you work on ary2, not A. Then you'll have the original indices left over with the surviving entries.

full compassBOT
#
Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.