class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.empty()) {
            // invalid input
            return -1;
        }
        int i = 0;
        int j = 1;
        int currentSum = nums[0];
        int maxSoFar = currentSum;
        while (i < nums.size() && j < nums.size()) {
            // decide whether to do one of three options:
            // add the jth element to your running sum
            // don't add the jth element to your running sum
            // start a new subarray starting from j
            if (currentSum+nums[j] > nums[j]) {
                currentSum = currentSum + nums[j];
            } else {
                i = j;
                currentSum = nums[j];
            }
            maxSoFar = std::max(maxSoFar, currentSum);
            j++;

        }
        return maxSoFar;
    }
};