题目:
思想:
这题不会,以为是双指针但是超时了,结果是前缀和算法。以下是灵神的解
通过前缀和,我们可以把子数组的元素和转换成两个前缀和的差,即
$$
\sum_{j=left}^{right} nums[j] = \sum_{j=0}^{right} nums[j]− \sum_{j=0}^{left-1} nums[j]=s[right+1]−s[left]
$$
既然说到了「子数组的元素和」,那么利用前缀和 s,将问题变为:
找到两个下标 i 和 j,满足 j<ij<ij<i 且 s[j]<s[i],最大化 i−j的值。
代码:
1 | class Solution: |
1 | class Solution: |