配列からの最大サブ配列の選択

Question

長さがnの配列が与えられている場合、配列の2つ以上の連続する要素を選択することができない場合に選択できる要素の最大合計を見つける必要があります。例えば;

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

私はこのコードを書いています。

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

このプログラムはn<1000について予想される出力を生成するが、大きい入力の実行時エラー（SIGSEGV）を示します。理由は何でしょうか？ より効果的なソリューションは、.....

Answer 1

使用動的プログラミングも歓迎

DP [I]：

1-用いる： "i" は、インデックス

7場合があるから最大第一及び第二の要素

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

例1：

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

出力：

例2：

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

出力：

Implementation in C

Answer 2

この問題には、かなり単純な動的プログラミングソリューションがあります。

アレイ内の各項目はバイナリ選択を表します。選択できるかどうかは、選択できます。しかし、2つの連続する項目が選択されている場合、次の項目は選択できません。我々は現在の項目がでない場合は、現在の項目がを選択した場合

最高の合計を選択した3つの合計

• 最高の合計を追跡する必要があり、アレイ内の各項目について、およびSO現在の項目が選択で、前の項目が

を選択した場合は、前の項目がは

最高の合計を選択しませんでした

#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配列の内容を見てみましょう。この例では、2つのエンドポイントが同じ合計を持つため、同じ回答を返す2つのパスが配列内にあります。 2つのパスは、次の選択肢を表します。

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