Maximum subsequence sum in an array with no 3 consecutive number

Question

I have to find the maximum sum in an array such that no 3 consecutive number together for eg 3 4 5 1 2 should return me 11. (4+5+2)

I am getting out as 9. I am using dynamic programming since I want the running time to be O(N) The idea is s array will store the max sum and s1 array will store the length of input seen to keep track of consecuent numbers

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class ex {       

    public static int maxSubArraySum(int a[], int size)
    {

       int s[]= new int[size+1];
       s[0]=0;
       int s1[]= new int[size+1];
       s1[0]=0;
       for (i = 1; i <= size; i++)
       {

            s1[i]= 1+s1[i-1];
            if(s1[i]<3) {
                int k=Math.max(s[i-1], a[i-1]+s[i-1]);       
                s[i]=k;
            }
            else {
                s[i]=Math.max(a[i-1], a[i-1]+a[i]);
                s1[i]=0;
            }
       }
       return s[s.length-1];
    }



    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner sc= new Scanner(System.in);
        int size=sc.nextInt();
        int a[]=new int[size];
        for(int i=0;i<size;i++) {
            a[i]=sc.nextInt();

        }
        System.out.println(maxSubArraySum(a, a.length));            

    }

}

Answer 1

I think your code requires a slight tweak, below are the changes you need to make

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class ex 
{       
    public static int maxSubArraySum(int a[], int size)
    {
       int s[] = new int[size+2];

       //they will form your base cases
       s[0] = 0;
       s[1] = a[0];
       s[2] = a[0] + a[1];

       for(int i = 2; i < size; i++)
       {
           s[i+1] = Math.max(a[i] + s[i-1], a[i] + a[i-1] + s[i-2]);
           s[i+1] = Math.max(s[i+1], s[i]); 
       }
       return s[size];
    }

    public static void main(String[] args) 
    {
        Scanner sc= new Scanner(System.in);
        int size=sc.nextInt();
        int a[]=new int[size];
        for(int i=0;i<size;i++) 
        {
            a[i]=sc.nextInt();
        }
        System.out.println(maxSubArraySum(a, a.length)); 
     }           
 }

Hope this helps.

Answer 2

Consider the array starts from index 0...n-1 i.e a[0...n-1],

we create array table[n+1] and table[i] means maximum sum from 1 to i without no three continuous numbers. While computing table[i], we have to choose whether to select i th element or not.

So, three cases are there

Case 1: Since, we can't select three consecutive numbers, but can select two consecutive numbers and skipping third one.

Case 2: select i th element and skip (i-1) th element.

Case 3: If we doesn't select i th element

So, based on above discussion c++ code is given below:

int max_sum_no_three_consecutive(int a[], int n)
{
    int table[n+1];
    table[0] = 0;
    table[1] = a[0];
    table[2] = a[1];    
    for (int i = 3; i <= n; i++) table[i] = max_3(table[i-1], table[i-2] + a[i-1], a[i-1] + a[i-2] + table[i-3]); 
        return table[n];
}

Answer 3

It's an old post but thought of answering the question.

for(int i = 0; i < input.length; i++) {
    if(0 == i) {
        sum[i] = input[0];
    } else if(1 == i) {
        sum[i] = input[0] + input[1];
    } else if(2 == i){
        sum[i] = getMaxOf3(sum[i - 1], sum[i-2] + input[i], input[i] + input[i - 1]);
    } else {
        sum[i] = getMaxOf3(sum[i - 1], sum[i - 2] + input[i], sum[i - 3] + input[i] + input[i - 1]);
    }
}

int getMaxOf3(int x, 
                 int y, 
                        int z) {
    return Math.max(Math.max(x, y), z);
}

Explanation:

Consider the array: {3, 4, 5, 1, 2}
we need to first have some default values for the result array.
sum[0] = array[0];
sum[1] = array[0] + array[1];
sum[2] = maximum of either (arr[0] + arr[1]) or (arr[1] + ar[2]) or (arr[0] + arr[2])

We calculated 3 sums,as we will be using these for furthur sum calculations.
    sum[3] = max(sum[2], sum[1] + arr[3], sum[0] + arr[3] + arr[2]);
This reduces to,
sum[i] = max(sum[i - 1], sum[i - 2] + arr[i], sum[i - 3] + arr[i] + arr[i - 1]);