In the Leetcode Maximum Subarray problem solution 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 <= 105
- -104 <= nums[i] <= 104
Solution in C Programming
int maxSubArray(int* nums, int numsSize){
int maxSum=-10000;
int currentSum=-10000;
int i;
for(i=0;i<numsSize;i++){
if(nums[i]>currentSum+nums[i]){
currentSum=nums[i];
}else{
currentSum=nums[i]+currentSum;
}
if(maxSum<currentSum)
maxSum=currentSum;
}
return maxSum;
}Solution in C++ Programming
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSub = nums[0], tempMax = nums[0];
for (int i = 1; i < nums.size(); i++) {
tempMax = max(nums[i], nums[i] + tempMax);
if (tempMax > maxSub) maxSub = tempMax;
}
return maxSub;
}
};Solution in Java Programming
class Solution {
public int maxSubArray(int[] nums) {
int i = 0, size = nums.length, sum = 0, max = nums[0];
while(i<size){
sum += nums[i];
if(sum > max){
max = sum;
}
if(sum <= 0){
sum = 0;
}
i++;
}
return max;
}
}Solution in Python Programming
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
current_sum = 0
max_sum = -sys.maxsize
for n in nums:
current_sum += n
max_sum = max(current_sum, max_sum)
if current_sum < 0:
current_sum = 0
return max_sumSolution in C# Programming
public class Solution {
public int MaxSubArray(int[] nums) {
int curr = 0;
int max = nums[0];
foreach (int n in nums) {
if (curr < 0) curr = 0;
curr += n;
max = Math.Max(max, curr);
}
return max;
}
}Also read,