Maximum Sum Subsequence Non-Adjacent

Revision en2, by phoaiphuthinh, 2017-12-28 12:25:25

I've a big problem: Given N number a[1],a[2],..,a[N] and M queries. (N,M <= 10^5)

Each query, change a[v] to x, and find the maximum sum subsequence such that no two elements are adjacent.

Example: a = {1,1,1,1,1,1}

  • First query, change a[5] to 3, thus a = {1,1,1,1,3,1} -> the answer is 5 (choose a[1],a[3],a[5])

  • Second query, change a[2] to 4, thus a = {1,4,1,1,3,1} -> the answer is 7 (choose a[2],a[5])

  • And so on..

I think use DP to solve this problem, but the complexity is O(N*M) can't run with N,M <= 10^5.

Could you help me? Thanks all.

Tags dynamic programming, dp, maximum sum subsequence, complexity optimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English phoaiphuthinh 2017-12-28 20:08:42 55 Tiny change: 'hanks all.' -> 'hanks all.\n\n**UPD:** I've solved this problem, thanks for all. '
en2 English phoaiphuthinh 2017-12-28 12:25:25 14 Tiny change: '<= 10^5.\nCould you help me?' -> '<= 10^5.\n\nCould you help me? Thanks all.'
en1 English phoaiphuthinh 2017-12-28 10:48:10 604 This comment automatically posted. (published)