Q3: 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.
Solution :
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int curMax = 0, maxTillNow = INT_MIN;
for(auto c : nums)
curMax = max(c, curMax + c),
maxTillNow = max(maxTillNow, curMax);
return maxTillNow;
}
};
Explantion:
.)Initialize two variables, curMax and maxTillNow to 0 and INT_MIN, respectively.
.)Iterate through each element (c) in the nums vector using a range-based for loop.
.)For each element, update curMax using the formula: curMax = max(c, curMax + c).
This represents the maximum sum subarray ending at the current index.
.)Update maxTillNow with the maximum value between its current value and curMax.
This ensures that it holds the maximum sum subarray encountered so far.
.)After the loop, maxTillNow contains the maximum sum subarray across the entire vector.
.)Return the value of maxTillNow.