## Table of contents

## Open Table of contents

## Problem

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`

**Follow up:** If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

## Explanation/Approach

This problem is a classic example of dynamic programming and can also be solved using divide and conquer. The key idea is to find the maximum sum of a contiguous subarray within a given one-dimensional array.

**Kadane’s Algorithm:**This dynamic programming approach involves iterating through the array and at each step, deciding whether to add the current element to the existing subarray or start a new subarray.

## Solution 1: Kadane’s Algorithm

```
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
```

**Time and Memory Complexity**

The time complexity is O(n) as it requires a single pass through the array. The space complexity is O(1) as it only uses a few variables.

**Explanation**

Kadane’s algorithm iterates through the array, updating the current subarray sum. If adding the current element results in a larger sum than the element itself, it is added to the current sum. Otherwise, the current sum is reset to the current element. The maximum sum is updated at each step.