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, Jul 28 '16 at 05:04
Please try using debugger first to determine where the SIGSEGV is caused. — MikeCAT, Jul 28 '16 at 05:04
It is given that `n<200000` and `arr[i]<10000`....will it cause overflow.. — yobro97, Jul 28 '16 at 05: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, Jul 28 '16 at 05:12
@user3386109 can you suggest another approach to this problem... — yobro97, Jul 28 '16 at 08:14
Possible duplicate of [Segmentation Fault - Large Array](http://stackoverflow.com/questions/24375801/segmentation-fault-large-array) — n. m. could be an AI, Jul 28 '16 at 12:08
@yobro97 Yup, I've posted an answer that shows an alternate approach to the problem. — user3386109, Jul 28 '16 at 19:44

Mojtaba Khooryani · Accepted Answer · 2020-04-03T11:36:16.280

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 03 '20 at 11:36

answered Jul 28 '16 at 11:35

Mojtaba Khooryani

1,763
1
17
36

The OP uses **C** and not **C++** – Michi Jul 28 '16 at 11:47
@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.. – yobro97 Jul 28 '16 at 13:27
@yobro97 added to end. check it. – Mojtaba Khooryani Jul 28 '16 at 13:55
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 Jul 28 '16 at 19:59
@AbdulelahAlJeffery you can send array(any size) to function and get answer :| – Mojtaba Khooryani Jul 28 '16 at 20:02
@AbdulelahAlJeffery 'your code is just for the example he provided n=5' why you say that?! I updated second example – Mojtaba Khooryani Jul 28 '16 at 20:11
1

+1 for the DP solution, it was an oversight from my part .. now I'm looking carefully to the code, definitely thumps up. – 7kemZmani Jul 28 '16 at 21:03

user3386109 · Answer 2 · 2016-07-29T01:03:42.743

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

Selection of maximum sub-array from the array

2 Answers2