這兩個指針算法

我想了解這兩個指針算法方法，所以我一直在讀this article 這兩個指針算法

因此，這裏的問題。假設我們有一個N個元素的數組。我們希望找到該數組中元素的最大連續序列，其中總和小於或等於M.我們必須返回元素序列總和的值。

所以假設我們有一組元素[2，1，3，4，5]，我們的M是12. 我們會返回12，因爲3,4和5總和爲12。從文章

我們在陣列的前端引入兩個指針l，r表示我們連續的子數組的startIndex和endIndex的，與他們兩個。
現在我們開始擴大我們的右指針r提供sum[l,r] <= M有一次，我們在達到這樣一個階段，我們沒有任何選擇，但移動左指針以及和開始下降的總和，直到我們在到達情況我們可以再次擴展我們的右指針。
當我們到達這一點時，我們需要移動左邊的指針，我們不斷更新我們迄今爲止取得的最大總和。

這裏是C++代碼。

#include <bits/stdc++.h> 
#define lli long long 
#define MAX 1000005 

using namespace std; 

lli A[MAX]; 

int main() 
{ 
    int n; 
    lli sum = 0;  
    cin >> n; 

    for (int i = 0; i < n; i++) cin >> A[i]; 

    int l = 0, r = 0; 
    lli ans = 0; 

    while (l < n) { 
     while (r < n && sum + A[r] <= M) { 
      sum += A[r]; 
      r++; 
     } 
     ans = max(ans, sum); 
     sum -= A[l]; 
     l++; 
    } 

    cout << ans << endl; 
    return 0; 
}

但我不明白爲什麼這種方法有效。我們沒有考慮所有可能的連續子序列。只要總和超過，我們就會記錄下我們當前的子序列長度，比較它是否大於前一個，然後簡單地增加l並重復該過程。

我不明白這是如何產生正確的結果。

來源

2017-04-06 Rockstar5645

你忘記了不僅l遞增，而且前一個「L」個元素的值正在與總和相除。然後總和包含新'L'和'R'之間的所有剩餘元素，不需要重新計算該總和（用'R = L'重新開始循環）。我也認爲（沒有讀過這篇文章），有一個隱含的要求是> = 0，所以總和只能增長。 – antipattern