53_maximum_subarray.cpp

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0], currSum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            currSum += nums[i];
            maxSum = max(maxSum, currSum);
            if (currSum < 0) {
                currSum = 0;
            }
        }
        return maxSum;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    Solution solution;
    int result = solve.maxSubArray(nums);
    cout << result << '\n';
    return 0;
}

/*
    ------------------
    Problem Statement:
    ------------------
    Given an integer array nums, find the subarray with the largest sum, and return its sum.

    ----------
    Example 1:
    ----------

    Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
    Output: 6
    Explanation: The subarray [4,-1,2,1] has the largest sum 6.

    ----------
    Example 2:
    ----------

    Input: nums = [1]
    Output: 1
    Explanation: The subarray [1] has the largest sum 1.

    ----------
    Example 3:
    ----------

    Input: nums = [5,4,-1,7,8]
    Output: 23
    Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
    
    ------------
    Constraints:
    ------------

    1 <= nums.length <= 10^5
    -10^4 <= nums[i] <= 10^4
*/