Table of Contents

## Question

Given an integer array `nums`

, find the contiguous subarray (containing at least one number) which has the largest sum and return *its sum*.

A **subarray** is a **contiguous** part of an array.

**Example 1:**

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

**Example 2:**

Input:nums = [1]Output:1

**Example 3:**

Input:nums = [5,4,-1,7,8]Output: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.

## Python Solution

class Solution: def maxSubArray(self, nums: List[int]) -> int: if len(nums)==1: print(nums[0]) global_max = nums[0] current_sum = nums[0] for i in range(1,len(nums)): current_sum = max(current_sum+nums[i],nums[i]) global_max = max(current_sum,global_max) return global_max