数组中和不超过某个数的最大连续区间

ridershen

kimi0428 发表于 12-4-2014 12:08 AM
  B" F- o) S$ DLZ, MaxRange1这个function会死循环. arr: [1, 2, 5, 3], budget = 9.

9 h+ f0 `- ~0 N7 rThanks.
' E1 |# q( D4 M0 o7 D4 F* R+ PI have corrected in the bottom. The thread itself is not editable.

ridershen

Correct the bug found by kimi0428. Hope it works fine now.
1 ?5 z6 [. l) {6 Z2 e$ x

1. int MaxRange1(const vector<int>& arr, int budget) {
     S  U  ?: k2 J
2.     int range = 0;
     M2 f; ?8 t  B8 G, ?  o
3.     int a, b;
   
4.     a = b = 0;
   + F6 `; Y' c5 u. S4 g
5.     int sum = 0;
   7 A. a0 v6 k5 r6 _
6.     int n = arr.size();
     W" B" I0 c2 M7 s
7.     while (true) {
   / Q* H4 g: ?9 M+ T
8.         while (b<n && sum + arr[b] <= budget) {
   - J; L% Y; a$ p: L
9.             sum += arr[b];
   5 T7 r/ P. m2 U! M$ g
10.             ++b;
    
11.         }
    / H! |6 g) Q' o' D/ F+ X! u
12.         range = std::max(range, b-a);
    
13.         if (b<n) sum += arr[b];
    + _( x( @# n3 Z
14.         else break;
    
15.         while (a<n && sum > budget) {
    
16.             sum -= arr[a];
    
17.             ++a;
    
18.         }
    
19.     }
    
20.     return range;
    $ T( ?% o8 J! k2 R$ g7 u1 s
21. }

复制代码

litaoye@263.net

不错的题目呀，cp啥时候帮我们做成OJ的问题？