Continuous Subarray Sum 2

TAG: subarray + 取反

数组可以循环，求此时的最大subarray

code

class ReturnType {
public:
    int s_index;
    int e_index;
    int maxvalue;
    ReturnType(int s_index, int e_index, int maxvalue)
    {
        this->s_index = s_index;
        this->e_index = e_index;
        this->maxvalue = maxvalue;
    }
};

class Solution {
public:
    /**
     * @param A an integer array
     * @return  A list of integers includes the index of 
     *          the first number and the index of the last number
     */
    vector<int> continuousSubarraySumII(vector<int>& A) {
        // Write your code here
        // Write your code here
        ReturnType pos = findMaxSubarray(A);
        int n = A.size();
        int totalsum = 0;
        for(int i = 0; i<A.size(); i++)
        {
            totalsum += A[i];
            A[i] = A[i]*-1;
        }
        ReturnType neg = findMaxSubarray(A);

        if(pos.maxvalue > totalsum + neg.maxvalue || pos.maxvalue < 0)
        {
            //cout<<"1"<<endl;
            vector<int> ret;
            ret.push_back(pos.s_index);
            ret.push_back(pos.e_index);
            return ret;
        }
        else
        {
            //cout<<"2"<<endl;
            vector<int> ret;
            ret.push_back((neg.e_index+1)%n);
            ret.push_back((neg.s_index-1+n)%n);
            return ret;
        }

    }

    ReturnType findMaxSubarray(vector<int>& A)
    {
        int minsum = 0;
        int sum = 0;
        int min_index = -1;
        int maxsum = INT_MIN;
        vector<int> max_sum_index(2, 0);

        for(int i = 0; i < A.size(); i++)
        {
            sum += A[i];
            if(sum - minsum > maxsum)
            {
                maxsum = sum-minsum;
                max_sum_index[0] = min_index+1;
                max_sum_index[1] = i;
            }

            if(sum < minsum)
            {
                minsum = sum;
                min_index = i;
            }
        }

        return ReturnType(max_sum_index[0], max_sum_index[1], maxsum);
    }

};