Algorithms Forever ...: Largest sum of elements with no three consecutive
int max_three(int[] input, int N){
}
Read full article from Algorithms Forever ...: Largest sum of elements with no three consecutive
Given a sequence of positive numbers, find the maximum sum that can be formed which has no 3 consecutive elements present.
For example: consider the sequence 3000 2000 1000 3 10 Here, the answer would be 5013, by taking 3000, 2000, 3 & 10. Note that we can't form a sequence that takes 3000, 2000 & 1000 together because they are the consecutive elements of the array.
Sample cases 1 2 3 ans=5
100 1000 100 1000 1 ans=2101
1 1 1 1 1 ans=4
1 2 3 4 5 6 7 8 ans=27
Try to find an O(N) solution. N is the number of elements in the array.
int max_three(int[] input, int N){
int sum[] = new int[N+2];
sum[0] = 0;
sum[1] = input[0];
sum[2] = input[0] + input[1];
for (int i=2; i<N ;++i){
sum[i+1] = max(input[i] + sum[i-1], input[i] + input[i-1] + sum[i-2]);
sum[i+1] = max(sum[i+1], sum[i]);
}
return sum[N];
Read full article from Algorithms Forever ...: Largest sum of elements with no three consecutive
