Monday, November 7, 2011

Largest Non Consecutive Subsequence

Given a sequence of N integers, devise an algorithm to find a sub-sequence S[] for which sum of its elements is maximum and such that S contains no two consecutive elements from input sequence.

Ex. input[] = [1 5 3 7 -2 -4 2]

Answer [5 7 2] Sum=14

Solution :
This requires Dynamic Programming formulation :
Let sum[i] represent maximum non-consecutive subsequence sum till ith element of input[], then
sum[i] = max(sum[i-1], input[i] + sum[i-2])

which says that new sum would either be obtained by not including ith element i.e previous sum, or by including it with last to previous sum i.e input[i-2]. The new sum would be maximum of these two possibilities.

Code :

int largest_non_consecutive(int input[], int N, int output[]){

int sum[N], jump[N], k=0, i;

sum[0] = input[0];

jump[0] = -2

if(input[1] > input[0]){

sum[1] =  input[1];
jump[1] = -1;
}
else {

sum[1] =  input[0];
jump[1] = 0;
}

for(i=2; i<N; i++){

if(sum[i-1] > input[i] + sum[i-2])){

sum[i] =  sum[i-1];
jump[i] = i-1;
}
else {

sum[i] = input[i] + sum[i-2];
// input[i] is included in resulting sequence when jump[i] is i-2
jump[i] = i-2;
}
}

// fill output according to jumps -- resulting sequence is in reverse order
for(i=N-1; i; i++){
if(jump[i] == i-2){
output[k++] = input[i];
}
}

return sum[N-1];
}

Complexity :

  • Time : O(N)
  • Space : O(1)

3 comments:

  1. this solution wont work. max can also be (sum[i-1]+input[i]) when sum[i-1] was calculated with not including input[i-1].

    ReplyDelete
  2. You speak of the case when input[i] is added to sum[i-1] when input[i-1] is not included. But remember here when [i-1] is not included, then sum[i-1] is equal to sum[i-2] so new sum[i] = input[i] + sum[i-2] handles all such cases in above code.

    ReplyDelete
  3. Its very obvious but you can use only 3 variables here, instead of using the sum[N] array.
    This is you code, but slightly modified.

    int sum(int inp[],int N)
    {
    int last,second_last,cur,i;
    second_last = inp[0];
    if(input[1] > inp[0])
    last = inp[1];
    else
    last = inp[0];
    for(i=2; i inp[i] + second_last)
    cur = last;
    else
    cur = inp[i] + second_last;
    second_last=last; last=cur;
    }
    return cur;
    }

    ReplyDelete