给定一个长度为 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)。可能是什么原因?
也欢迎更有效的解决方案.....
最佳答案
使用动态规划
DP[i]:来自“i”索引的最大值
有7种情况:
1-使用第一个和第二个元素
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));
输出:
23
例子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));
输出:
496
关于c - 从数组中选择最大子数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38627427/