c - 优化线性矩阵的利润，用户可以跳过 1 或 2 个单元格

Question

说明:几个单元格依次排列成一条直线。在第 i 个单元格中，写入给定整数 ai (i=1,2, …, N)。我从左端的第一个单元格开始向右移动；我可以选择跳进下一个单元格，或者跳进下一个单元格的下一个。每次进入牢房i，我都要付钱 |艾 |美元，当 ai 为负时，或接收 ai 美元，当 ai 为非负时。我最多能赚多少钱？

输入:N, a1, a2, …., aN 的整数值，以空格分隔。

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

约束条件:0 < N < 100； -100 < ai < 每个 ai 100。

例如

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

输出: 10

我已经想出了一个我认为正确的问题解决方案。但是，提交测试员只给我 5/10。

#include <stdio.h>

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


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

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

 printf("%d", sum);

 return 0;
}

尽管我似乎能够在约束范围内输入随机输入后获得稳定的输出，但代码仅通过了 5/10 测试。您能指出您在代码中注意到的任何违规行为吗？

Answer 1

考虑

0 -1 -2 -1000 0

当 i = 1 时，您的算法将执行第 25 行的分支，因此选择 0 -1 -2 0 个细胞，虽然最优解是 0 -2 0