非重叠连续子阵列的最大长度总和

我试图实施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)

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

来源

2017-08-11 Jayesh

[OT]：你可以简化你的代码，就像[that]（http://ideone.com/fj8JvB） – Jarod42

随着while(a[i] <= k && i++ < ele)你实际上可以走出阵列a，导致undefined behavior。

如果i是数组的最后一个索引，然后i++ < ele实际上是true（因为后缀++操作返回增量前的老值），然后在循环i将出界。

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

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

来源

2017-08-11 08:53:24

isnt已经是UB，因为出现'i ++'和'a [i]'在相同的表达？ – user463035818

@ tobi303不，左侧在“&&”或“||”表达式的右侧之前排序（参见例如[this evaluation order reference]（http://en.cppreference.com/w）/cpp/language/eval_order），尤其是[rule]（http://en.cppreference.com/w/cpp/language/eval_order#Rules）6）。 –

不同while(i < ele && a[i++] <= k)和while(a[i] <= k && i++ < ele)之间是： while(i < ele && a[i++] <= k)将增加i第一和后来得到价值，但while(a[i] <= k && i++ < ele)将比较i和ele第一和增加i后。

因此，在你的代码，当程序运行的while(a[i] <= k && i++ < ele)，i等于3，但while(i < ele && a[i++] <= k)等于4。这就是为什么这个问题造成的原因

来源

2017-08-11 08:58:41

非重叠连续子阵列的最大长度总和

回答

相关问题