Ehsan_sShuvo's blog

How to find the sum of all possible subsequences multiplication of the array?
By Ehsan_sShuvo, history, 7 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?
»
7 years ago, # |
  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
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry,,i can't get any proof though it works well :) Thank you .Could you please help me to get the proof of your solution?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Proof by induction on size of array.

      It's true for size = 1. Inductive step : moving from i-1 to i, use the recurrence mentioned in NMouad21's comment.

      → Reply
»
7 years ago, # |
← 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