优化的线性矩阵的利润，其中用户可以跳过1层或2的细胞

Question

指令：几个细胞在一条直线上排列的一个接一个的。在第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

我想出了一个解决方案，我认为这是正确的问题。然而，提交测试只给我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