## Algorithm

Problem Name: 53. Maximum Subarray

Given an integer array `nums`, find the

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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int maxSubArray(int* nums, int numsSize) {
int i, s, m = 0;
m = s = nums[0];
for (i = 1; i < numsSize; i ++) {
//printf("s: %d, m: %d\n", s, m);
if (s > 0) s += nums[i];
else       s  = nums[i];
if (m < s) m = s;
}
//printf("s: %d, m: %d\n", s, m);
return m;
}
``````
Copy The Code &

Input

cmd
nums = [-2,1,-3,4,-1,2,1,-5,4]

Output

cmd
6

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int maxSubArray(vector& nums) {
vectordp(nums.size());
dp[0] = nums[0];
int maxSum = dp[0];
for(int i = 1; i < nums.size(); i++){
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
};

``````
Copy The Code &

Input

cmd
nums = [1]

Output

cmd
1

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maxSubArray = function (nums) {
let res = -1e9, sum = 0
for(const e of nums) {
sum += e
res = Math.max(res, sum)
if(sum < 0) sum = 0
}
return res
}
``````
Copy The Code &

Input

cmd
nums = [5,4,-1,7,8]

Output

cmd
23

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maxSubArray(self, nums):
sm, mn, mx = 0, 0, -float("inf")
for num in nums:
sm += num
mx, mn = max(mx, sm - mn), min(mn, sm)
return mx
``````
Copy The Code &

Input

cmd
nums = [-2,1,-3,4,-1,2,1,-5,4]

Output

cmd
6

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _053_MaximumSubarray
{
public int MaxSubArray(int[] nums)
{
if (nums.Length == 0) return int.MinValue;
int currSum = nums[0], maxSum = nums[0];

for (int i = 1; i < nums.Length; i++)
{
currSum = Math.Max(nums[i], currSum + nums[i]);
maxSum = Math.Max(maxSum, currSum);
}
return maxSum;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [1]

Output

cmd
1