Maximum subarray sum

• Time : $O(n)$
• Space : $O(1)$

c++

int maxSequence(const std::vector<int>& arr){
    int res = 0, mi = 0, now = 0;
    for(int i = 0; i < arr.size(); i++) {
        now += arr[i];
        res = std::max(res, now - mi);
        mi = std::min(mi, now);
    }
    return res;
}