Design and write, in pseudocode, a dynamic programming algorithm that solves the following problem. Input: A...

Transcribed Image Text:

Design and write, in pseudocode, a dynamic programming algorithm that solves the following problem. Input: A sequence S of positive integers, and its length n Output: The subsequence S' of largest total sum, such that: if two consecutive elements of S are in S', then their sum is odd. Note: this is equivalent to saying that if element S; is in S", then element Si+1 can only be in S' if it has different parity than S; (one is odd, the other is even). Design and write, in pseudocode, a dynamic programming algorithm that solves the following problem. Input: A sequence S of positive integers, and its length n Output: The subsequence S' of largest total sum, such that: if two consecutive elements of S are in S', then their sum is odd. Note: this is equivalent to saying that if element S; is in S", then element Si+1 can only be in S' if it has different parity than S; (one is odd, the other is even).

Answer rating: 100% (QA)

this code is working fine and time complexcity is O... View the full answer