二指针算法

Question

我试图理解两指针算法的方法，所以我一直在阅读本文

所以这是问题。假设我们有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并重复该过程。

我看不出如何产生正确的结果。