非重疊連續子陣列的最大長度總和

我試圖實施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

非重疊連續子陣列的最大長度總和

回答

相關問題