Maximum Subarray

 Problem Statement: 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: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Source: https://leetcode.com/problems/maximum-subarray/

Leetcode Difficulty: Easy

Asked in: Amazon ,

Code:

    def maxsubarray(self, nums: List[int]) -> int:
        curr_sum=nums[0]
        final_sum=curr_sum
        for i in nums[1:]:
            if curr_sum<0: curr_sum=0
            curr_sum += i
            final_sum = max(curr_sum, final_sum)
        return final_sum

Thought Process / Explanation:

It's a pretty standard problem that uses Kadane's Algorithm.

Thank You!