從陣列中選擇最大子陣列

Question

給定一個長度爲n的數組，如果不允許選擇超過兩個連續的陣列元素，則需要找到可以選擇的元素的最大總和。例如;

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

這個問題有一個相當簡單的動態編程解決方案。

數組中的每一項表示一個二元選擇：它可以被選擇或不被選擇。但是如果選擇了兩個連續的項目，則不能選擇下一個項目。所以對於陣列中的每個項目，我們需要保持三個總和

• 最好的總和軌道如果當前項不選擇
• 最好的總和，如果當前項目爲選擇，和前一個項目是不選擇
• 最好的總和如果當前項目選擇，和以前項被選定

下面的代碼：

#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