Choosing the maximum submatrix from an array

Question

Given an array of length n, it is necessary to find the maximum amount of elements that can be selected if it is not allowed to select more than two consecutive elements of the array. For instance:

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

So, I wrote 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 a runtime error (SIGSEGV) for large inputs. What is the reason? More effective solutions are also welcome .....

Answer 1

use dynamic programming

DP [i]: maximum from index "i"

There are 7 cases:

1- use the first and second elements

2-

3-

4-

5

6 -

7 -

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));

:

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));

:

496

C

Answer 2

.

: . , .

• ,
• , ,
• ,

:

#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]) );
}

208. , , dp:

, dp . , , . :

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