Ehsan_sShuvo's blog

How to find the sum of all possible subsequences multiplication of the array?
By Ehsan_sShuvo, history, 8 years ago, In English

How could i solve this problem.Please help me to solve this problem. Thanks in advance :)

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

It is just (A1 + 1)(A2 + 1)...(An + 1) - 1. Expand it for proof.

→ Reply
»
8 years ago, hide # |
← Rev. 3  
Vote: I like it +10 Vote: I do not like it

You can solve it by a simple O(n) DP approach.

let's suppose we have the answer to the prefix array ending at i — 1. if we add one element, which is a[i] then the answer for the prefix ending at i is:

ans[i] = ans[i — 1] + ans[i — 1]*a[i] + a[i];

  • ans[i — 1] << case where we don't include a[i] in the previous calculated subsequences
  • ans[i — 1]*a[i] << case where we include it
  • a[i] << case where we take it alone

and finally, the answer is just ans[n] of course

Here's an example code: https://ideone.com/VbqE9b

→ Reply