首页 > 试题广场 >

给定一个数组，可以从数组中取出下标不连续的任意个数

[单选题]

给定一个数组，可以从数组中取出下标不连续的任意个数，求可以取出的数的和的最大值，例如：给出数组A[]={1,2,2,5,3,4,3}可以取出的最大和为2+5+4=11。现再给定数组{3,9,7,5,1,3,1,2,7}，能取出的数的和的最大值是

```
38
```
```
24
```
```
22
```
```
19
```

查看答案及解析

牛客148381号

http://blog.csdn.net/yang20141109/article/details/51169991

发表于 2016-04-16 20:47:51 回复(0)

菜小豆

9 5 3 7；

如果严格证明的话，应该需要动态规划的方法。

发表于 2015-09-28 14:30:35 回复(0)

xttty

f[i]=max{f[i-2]+a[i],f[i-1]} f[i]表示前i个数中能取到的最大值

发表于 2017-03-08 17:14:54 回复(0)

麦子神探

从下标3开始i表示，j从i-2开始递减（不能取相邻的那个i-1），找0~i-2中的max，记录到当前辅助i。

发表于 2016-08-04 14:32:30 回复(0)

忆水寒

9 5 3 7

发表于 2016-07-21 14:24:35 回复(0)

196309yang

   int a[]={3,9,7,5,1,3,1,2,7};
int b[9]=  {0,0,0,0,0,0,0,0,0};
void findmax(int index,int lenth,int currentmax)
{
    if(index>=lenth)
    {
        cout<<currentmax<<endl;
        for(int j=0;j<9;++j)
        cout<<b[j]<<"  ";
        cout<<endl;
       // currentmax=0;
        return;
    }

        for(int i=0;i<2;++i)
        {
            if(i==0)
            {
                currentmax+=a[index];
                b[index]=1;
                findmax(index+2,lenth,currentmax);
                b[index]=0;
                currentmax-=a[index];
            }
            if(i==1)
            {
                //currentmax+=a[index+1];
                findmax(index+1,lenth,currentmax);
            }
        }
}
int main()
{
   int findmax1=0;
       findmax(0,9,findmax1);
return 0;
}

编辑于 2015-09-29 17:24:35 回复(1)