Continuous Subarray Sum

http://www.lintcode.com/en/problem/continuous-subarray-sum/

maximum subarray index version

sum[i][j] = prefix[j] - prefix[i];

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> continuousSubarraySum(vector<int>& A) {
        // Write your code here
        vector<int> ret(2, 0);

        if(A.size() == 0)
        {
            return ret;
        }

        int minsum = 0;
        int sum = 0;
        int maxsum = INT_MIN;
        int minsum_index = -1;

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

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

        return ret;
    }
};