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
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 :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.
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]){
else {
for(i=2; i<N; i++){
// fill output according to jumps -- resulting sequence is in reverse order
for(i=N-1; i; i++){
return sum[N-1];
}sum[0] = input[0];
jump[0] = -2
if(input[1] > input[0]){
sum[1] = input[1];
jump[1] = -1;
}jump[1] = -1;
else {
sum[1] = input[0];
jump[1] = 0;
}jump[1] = 0;
for(i=2; i<N; i++){
if(sum[i-1] > input[i] + sum[i-2])){
else {
}
sum[i] = sum[i-1];
jump[i] = 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;
}// 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)
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].
ReplyDeleteYou 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.
ReplyDeleteIts very obvious but you can use only 3 variables here, instead of using the sum[N] array.
ReplyDeleteThis 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;
}