Blog # 65 : Maximum sum [A different version]

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. Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: Take a look again, think more. Hit again for hints. Hints: The solution for this problem is by dynamic programing. Hit again for solution Solution: Complexity: 1. TIme : O(N) 2. Space : O(N) Code: 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]; }