题解 | #子数组的最大累加和问题#

class Solution {
public:
    /**
     *
     * @param arr int整型vector the array
     * @return int整型
     */
    /*
    【双指针】
    从右指针进数，从左指针出数

*/
    int maxLength(vector& arr) {
        // write code here
        //invalid input
        if(arr.empty())
            return 0;
        //init
        map map;            // value-index
        int left = 0;
        int right = 1;
        map[arr[0]] = 0;
        int maxLength = 1;           //记录最大连续不重复子序列长度

        //假设 left--right 为连续不重复段
        while(left<=right && right<arr.size()){    //[left,right]
            //待加入元素 arr[right]重复，先删除再加入
            if(map.count(arr[right])){
                //从left删除至与arr[right]等值元素
                while(arr[left]!=arr[right]){
                    map.erase(arr[left]);
                    ++left;
                }
                ++left;
            }
            //加入arr[right]
            map[arr[right]] = right;
            maxLength = max(maxLength, right - left + 1);
            ++right;
        }
        return maxLength;
    }
};