c++ - 非重叠连续子数组的最大长度和

Question

我正在尝试实现 amazon面试题。

Find the maximum sum of lengths of non-overlapping contiguous subarrays with k as the maximum element.
Ex: Array: {2,1,4,9,2,3,8,3,4} and k = 4
Ans: 5
{2,1,4} => Length = 3
{3,4} => Length = 2
So, 3 + 2 = 5 is the answer

我有实现程序:

#include <iostream>
using namespace std;

int main()
{
        int a[] = {2,1,4,9,2,3,8,3,4,2};
        int cnt = 0, i = 0, j = 0, ele, k = 4;
        int tmp = 0, flag = 0;

        ele = sizeof(a)/sizeof(a[0]);

        for(j = 0; j < ele; )
        {
                i = j;
              //while( i < ele && a[i++] <= k) //It's working fine
                while(a[i] <= k && i++ < ele)  // It's not work
                {
                        cnt++;
                        cout<<"while"<<endl;
                }

                while(j < i)
                {
                        if(a[j++] == k)
                        {
                                flag = 1;
                        }
                }

                if(flag == 1)
                {
                        tmp += cnt;
                        flag = 0;
                }
                cnt = 0;
                j = i;
        }
        cout<<"count : "<<tmp<<endl;
        return 0;
}

在我的程序中，我使用了

while( i < ele && a[i++] <= k)

它工作正常并提供正确的输出。

但是，如果我使用

while(a[i] <= k && i++ < ele)

然后我的程序卡住了。为什么？

Answer 1

与 while(a[i] <= k && i++ < ele)你实际上可以越界a , 导致 undefined behavior .

如果i是数组的最后一个索引，那么i++ < ele实际上是true (因为后缀 ++ 运算符在递增之前返回 old 值)，然后在循环中 i将出界。

未定义的行为，好吧，未定义，可能意味着几乎任何事情都可能发生。从崩溃到无限循环或卡住循环。

更好的解决方案是使用 prefix 增量代替，如 ++i < ele .