一个算法作业问题:细胞矩阵扫描问题[关闭]

问题描述 投票:0回答:2

指令:几个细胞在一条直线上排列的一个接一个的。在第i个小区中,给定整数AI被写入(I = 1,2,...,N)。我从第一个单元格开始在左端和向右移动;我可以选择跳入下一个单元格,或进入下一个下一个单元格中。我进入了一个小区i每一次,我要付出| AI |元,当AI是否定的,或者接收AI美元,当AI是负数。至多,有多少美元就可以收入?

输入:由空格分隔N,A1,A2,...,AN,的整数值。

输出:一个整数等于想要的利润。

限制条件:0 <N <100; -100 <AI <100为每个AI。

EG

输入:7 2 -1 3 -2 -1 6 -5

输出:10

我做了该解决方案的一个烂摊子。如果任何人有任何建议,我将非常感激!

这是我走到这一步:

#include <stdio.h>


int main()
{
 int n,array[100];
 int i = 0;
 int sum = 0;


 if(scanf("%d",&n)){};
 for(i=0;i<n;i++){
    if(scanf("%d",&array[i])){}
 }

 for(i=0;i<n;i++)
 {
     if(array[i] >= array[i+1])
     {
        if(array[i+1] >= array[i+2])
        {
            if(array[i+2] > array[i+3])
            {
                sum += array[i+1];
                i++;
            }
            sum += array[i];
        }
        else if(array[i+1] < array[i+2])
        {
            if(array[i] >= array[i+2])
            {
                sum += array[i];
            }
            else if(array[i] < array[i+2])
            {
                sum += array[i+1];
                i++;
            }
        }
     }
     else if(array[i] < array[i+1])
     {
        if(array[i+1] < array[i+2])
        {
            if(array[i] < array[i+2])
            {
                sum += array[i+1];
                i++;
            }
            else if(array[i] >= array[i+2])
            {
                sum += array[i];
            }
        }
        else if(array[i+1] >= array[i+2])
        {
            sum += array[i];
        }
     }
 }

 printf("%d", sum);

 return 0;
}

什么是由该指令所施加的约束内的阵列中数字最大的可能的总和(可以跳过到i和i + 1)?

c algorithm loops
2个回答
1
投票

for(i=0;i<n;i++)
{
   if(array[i] >= array[i+1])

i == n-1当您访问array[n]这超出阵列的还是未初始化

当您访问类似问题array[i+2]array[i+3]

最小的变化,你可以无需修改算法做(我不明白坦白)是更换第二

for(i=0;i<n;i++)

通过

for(i=0; i<(n-2); i++)

并取代

if(array[i+2] > array[i+3])

通过

if(((i + 3) < n) && (array[i+2] > array[i+3]))

这是非常奇怪:

if(scanf("%d",&n)){};

我鼓励你做这样的事情:

if ((scanf("%d",&n) != 1) || (n > 100) || (n <= 0)) {
  puts("invalid number of cells");
  return 0;
}

对于剩下的我真的不明白你要计算什么


0
投票

至于IM相关的计算机只能和旁边的第二下一个整数之间的决定,但我们不知道,如果在这个阶段很好的选择将导致更糟糕的结束,例如序列可以是:

1 -2 -5 -40 -35 7

在这里,当电脑会将-2和-5它会选择-2与-34最终成为最好的情况下,而如果它是选择-5它可以用-32告终。

所以我的猜测是,你无法计算“最大总和”,除非你蛮力。


推荐问答