Selection of maximum sub-array from the array

Question

Given an array of length n, it is required to find the maximum sum of elements one can choose if it is not allowed to choose more than two consecutive elements of the array. For example;

n=5;
arr[5] = {10,3,5,7,3};
Output : 23
10+3+7+3=23

So I have written this code;

#include <stdio.h>
#include <stdlib.h>
int max=0;
void solve(int arr[],int ind,int sum,int n,int count)
{
    if(ind==n){
          if(sum>max)
              max=sum;
      }
      else{
          sum+=arr[ind];
          if(ind==n-1)
            solve(arr,ind+1,sum,n,1);
          if(ind==n-2 && count>1)
            solve(arr,ind+2,sum,n,1);
          if(ind<n-1 && count<2){
              count++;
              solve(arr,ind+1,sum,n,count);
          }
          if(ind<n-2)
              solve(arr,ind+2,sum,n,1);
          if(ind<n-3)
              solve(arr,ind+3,sum,n,1);
      }
}
int main()
{
    int n;
    scanf("%d",&n);
    int i=0,arr[n];
    while(i<n){
        scanf("%d",&arr[i]);
        i++;
    }
    int count=1;
    //going into all three possibilities
    solve(arr,0,0,n,count);
    solve(arr,1,0,n,count);
    solve(arr,2,0,n,count);
    printf("%d\n",max);
    return 0;
}

This program produces the expected outputs for n<1000 but shows runtime error (SIGSEGV) for larger inputs. What may be the reason? More effective solutions are also welcome.....

Maybe stack overflow caused by too-deep recursion? But the number may be too small to cause it? — MikeCAT
– MikeCAT, Commented Jul 28, 2016 at 5:04
Please try using debugger first to determine where the SIGSEGV is caused. — MikeCAT
– MikeCAT, Commented Jul 28, 2016 at 5:04
It is given that n<200000 and arr[i]<10000....will it cause overflow.. — yobro97
– yobro97, Commented Jul 28, 2016 at 5:05
You've got about 30 bytes of information on the stack for each level of recursion. So n=33000 will put about 1 megabyte on the stack. That could be enough to overflow the stack. — user3386109
– user3386109, Commented Jul 28, 2016 at 5:12
@user3386109 can you suggest another approach to this problem... — yobro97
– yobro97, Commented Jul 28, 2016 at 8:14

Mojtaba Khooryani · Accepted Answer · 2020-04-03 11:36:16Z

6

use dynamic programming

DP[i]: maximum from "i" index

there are 7 cases:

1- use the first and second elements

2- use the second and third elements

3- use the first and third elements

4- use only the first element

5- use only the second element

6- use only the third element

7- use none of the elements

int F(int[] a)
    {
        if (a.Length == 1)
        {
            return Max(a[0], 0);
        }
        int n = a.Length;
        int[] DP = new int[n];
        DP[n - 1] = Max(a[n - 1], 0);
        DP[n - 2] = DP[n - 1] + Max(a[n - 2], 0);
        for (int i = n - 3; i >= 0; i--)
        {
            DP[i] = Max(a[i], 0) + Max(a[i + 1], 0) + (i + 3 < n ? DP[i + 3] : 0);// first and second
            DP[i] = Max(DP[i], Max(a[i + 1], 0) + Max(a[i + 2], 0) + (i + 4 < n ? DP[i + 4] : 0));// second and third
            DP[i] = Max(DP[i], Max(a[i + 0], 0) + Max(a[i + 2], 0) + (i + 4 < n ? DP[i + 4] : 0));// first and third
            DP[i] = Max(DP[i], Max(a[i + 0], 0) + (i + 2 < n ? DP[i + 2] : 0));// first
            DP[i] = Max(DP[i], Max(a[i + 1], 0) + (i + 3 < n ? DP[i + 3] : 0));// second
            DP[i] = Max(DP[i], Max(a[i + 2], 0) + (i + 4 < n ? DP[i + 4] : 0));// third
            DP[i] = Max(DP[i], DP[i + 1]);// none
        }
        return DP[0];
    }

example1:

int[] a = new int[] { 10, 3, 5, 7, 3 };
writer.WriteLine(F(a));

output:

23

example2:

int[] a = new int[] { 1, 5, 2, 6, 9, 8, 20, 12, 41, 3, 0, 9, 95, 6, 74, 85, 20, 14, 26, 35, 14, 72, 15 };
writer.WriteLine(F(a));

output:

496

Implementation in C

edited Apr 3, 2020 at 11:36

answered Jul 28, 2016 at 11:35

Mojtaba Khooryani

1,8952 gold badges19 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Michi Over a year ago

The OP uses C and not C++

yobro97 Over a year ago

@mojtaba357 could you please convert the above code to c as Michi mentioned......I could understand the basic idea though....it would be more helpful to me if in c....Thanks..

Mojtaba Khooryani Over a year ago

@yobro97 added to end. check it.

7kemZmani Over a year ago

the OP is looking for solution that scale to an array of length n, and your code is just for the example he provided n=5. how would you change your code to scale to an array of any size?

7kemZmani Over a year ago

+1 for the DP solution, it was an oversight from my part .. now I'm looking carefully to the code, definitely thumps up.

|

user3386109 · Accepted Answer · 2016-07-29 01:03:42Z

This problem has a fairly simple dynamic programming solution.

Each item in the array represents a binary choice: it can either be selected or not. But if two consecutive items are selected, then the next item cannot be selected. So for each item in the array we need to keep track of three sums

the best sum if the current item is not selected
the best sum if the current item is selected, and the previous item was not selected
the best sum if the current item is selected, and the previous item was selected

Here's the code:

#include <stdio.h>

#define max3(a) (a[0]>a[1] ? a[0]>a[2]?a[0]:a[2] : a[1]>a[2]?a[1]:a[2])

int main( void )
{
    int array[] = { 10,3,7,55,60,62,4,2,5,42,8,9,12,5,1 };
    int N = sizeof(array) / sizeof(array[0]);
    int dp[N][3];

    dp[0][0] = 0;
    dp[0][1] = array[0];
    dp[0][2] = 0;
    for ( int i = 1; i < N; i++ )
    {
        dp[i][0] = max3(dp[i-1]);
        dp[i][1] = dp[i-1][0] + array[i];
        dp[i][2] = dp[i-1][1] + array[i];
    }
    printf( "%d\n", max3(dp[N-1]) );
}

The output of this program is 208. To understand how that was computed, take a look at the contents of the dp array:

Note that the correct path through the dp array is not known until the end. In this example, two endpoints have the same sum, so there are two paths through the array that give the same answer. The two paths represent these choices:

array:  10  3  7 55 60 62  4  2  5 42 8  9 12 5  1 
red:    10    +7   +60+62    +2   +42+8   +12+5     = 208  
blue:   10    +7   +60+62       +5+42   +9+12   +1  = 208

Collectives™ on Stack Overflow

Selection of maximum sub-array from the array

2 Answers 2

7 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related