Skip to main content

Maximum Non-Contiguous Sum of a Series

Given an arbitrary series, we've to calculate the maximum sum confined to only one restriction-
If we choose any number a [ i ] to calculate the sum, we can't choose a [ i+1 ]
Let's take a series: a[ ]= {1,2,3,4,5,9}

Linear Solution: Take two variable inc and exl. inc will store value if we choose a [ i ] to calculate the sum & exl will store value if we do not choose a [ i ], for any 0 ≤ i ≤ n. Now for every step, we have to calculate inc and exl. After iteration ends, max( inc,exl ) is the maximum non-contiguous sum. Roughly-

Why inc = exl + a [ i ] ? because the already calculated exl is from i-2. So if we choosed inc=  inc + a [ i ] , that would be a contiguous sum. exl is maximum of inc & exl right until  i-1.
Top Down solution( DP ): If you're familiar with dynamic programming, you know that, we need to calculate dp[n] - the maximum non contiguous sum at nth index.
Now we can have two possible state, we'll select the maximum one.
dp[ i ] = a [ i ] + dp [ i-2 ]   choosing i'th value
dp[ i ] = a [ i-1 ] + dp [ i-3 ]  choosing the value before i'th
Labels:

Comments

Post a Comment

Popular posts from this blog

SPOJ - GSS1

Considering input series: { 4 , -10 , 3 , 100 , -20 , 1 } Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y } A node contains-  [ START & END is a node's segment limit ] Prefix is the maximum sum starting at START, end can be anywhere. There are two possibilities of the maximum. One, node's leftChild's prefix or two, adding leftChild's sum + rightChild's prefix. (which will make the prefix contiguous) Suffix is the maximum sum ending at END, start can be anywhere. There's two possibility of the maximum. One, node's rightChild's already calculated suffix or two, add rightChild's sum + leftChild's suffix   (which will make the suffix contiguous). Sum : leftChild's sum + rightChild's sum. MAX Maximum of  -  prefix (result is in the node, starts from START but doesn't end in END ) suffix  (result is in the node, doesn't start from START but surely ends in END ) leftChild's max ( result is in left ...
14 comments
Read more

SPOJ 95 - STPAR - Street Parade

Problem Statement Heuristics:   Let, N be the number which is next in fixed order. Take an input X , if it is equal to N then next number will be n++. If not, then search for N in the side lane and after finishing the search, put X in the side lane. After all X is processed but N is not found in either X or side lane, then the order is not possible. Solution:
Post a Comment
Read more

SPOJ 394- ACODE

Problem Statement As from the problem-tag, you can see this is a DP( Dynamic Programming ) problem. Don't know Dynamic Programming? Here are some articles: Codechef , TopCoder . Try to solve a sample problem, for example, Fibonacci Numbers. Let's start cracking the problem. To solve a DP problem, the hardest and important part is to find the relation between previous or next steps and current step . We need to find out how the solution of the current step depends on its previous steps or next steps. Looking at:      2 5 1 1 4        from left to right Step 1: You can only interpret this as 2(B). Decoding- B EAAD  So, DP[1] = 1 Step 2: This can be 5(E) or collaborating with 2, it can be 25(Y). Result is BE AAD + Y AAD . So, DP[2] = 2 Step 3: Can only be interpreted as 1(A). 51 is not valid, as stated in problem. BEA AD + YA AD . DP[3] = 2.  Step 4: Will be interpreted as 1(A). BEAA D + YAA D+... ...
Post a Comment
Read more