第四十题 上一题的修改 不只是保存最大值，还要返回结果
要记录 最大的长度，当长度变了或者结果变了就要更新
第一种 忘记优化了，不用每次都更新，只要最后知道位置就能更新 但是可以用来理解 啥时候要更新 以及更新的是哪几个
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // 和上一题类似，但是返回结果变了
        
        // 因为有负数，所以不知道是否要往后加。其实可以知道，如果加上负数，数字小于0了，那么显然就不要加了
        int temp=0,max=-100000;
        int old_len=0;
        int new_len=0;
        vector<int> ret_ans;
        // 从前向后遍历
        for(int i =0;i<array.size();i++)
        {
            // 如果说 加上了数组中的值，整体变负的了，就说明前面这一串 和后面的数字肯定是分开来的
            // 那么就让temp重新开始统计往后的数字
            if(temp<0){
                new_len=1;
                temp=array[i];
            }
            else{
                new_len++;
                temp += array[i];
            }
            // 当temp更大，就要处理返回的结果了
            // 即使temp==max，还要判断长度是否比原来长
            if(temp>=max)
            {
                // 若果说结果一样但是长度没原来长，不用处理
                // 但是新来的更长 就要更新结果了。
                if(old_len<new_len){
                    ret_ans.clear();
                    for(int j=0;j<new_len;j++){
                        // 插入新的结果，最后 在反转
                        ret_ans.push_back(array[i-j]);
                    }
                    reverse(ret_ans.begin(),ret_ans.end());
                }
                max=temp;
            }
        }
        return ret_ans;
    }
};


第二种 算法一样 但是存储返回结果的时候 修改了一下
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // 和上一题类似，但是返回结果变了
        
        // 因为有负数，所以不知道是否要往后加。其实可以知道，如果加上负数，数字小于0了，那么显然就不要加了
        int temp=0,max=-100000;
        int old_len=0;
        int new_len=0;
        int point=0;
        // 从前向后遍历
        for(int i =0;i<array.size();i++)
        {
            // 如果说 加上了数组中的值，整体变负的了，就说明前面这一串 和后面的数字肯定是分开来的
            // 那么就让temp重新开始统计往后的数字
            if(temp<0){
                new_len=1;
                temp=array[i];
            }
            else{
                new_len++;
                temp += array[i];
            }
            
            // 首先，当temp更大，就要处理返回的结果了
            // 其次，如果temp==max，还要判断长度是否比原来长
            // 更新一下，保存的结果不用每次都更新，最后一次把要的存进去就好，前面只要保存要保存的位置
            // 而且保存结果不需要遍历了一个个存，直接截取array就好了
            // 记录下末尾的位置和长度 一会儿返回结果的时候直接截取就好了
            if(temp>max || (temp==max && old_len<new_len))
            {
                // 若果说结果一样但是长度没原来长，不用处理
                // 但是新来的更长 就要更新结果了。
                point=i;
                max=temp;
                old_len=new_len;
            }
        }
        // 之前的point是访问数组是确定的，下标0开始，后面要用的话要+1
        point++;
        // cout<<point<<" "<<old_len<<endl;
        // 更新一下，保存的结果不用每次都更新，最后一次把要的存进去就好，前面只要保存要保存的位置
        return {array.begin()+point-old_len,array.begin()+point};
    }
};