Maximum Subarray

Try to solve the Maximum Subarray problem.

We'll cover the following

Statement#

Given an integer array, nums, find the contiguous subarray that has the largest sum and return its sum.

Note: A subarray is a contiguous part of an array that contains at least one number.

Constraints:

  • 1≤1 \leq nums.length ≤103\leq 10^3

  • −104≤-10^4 \leq nums[i] ≤104\leq 10^4

Examples#

Created with Fabric.js 3.6.6

1 of 2

Created with Fabric.js 3.6.6

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Maximum Subarray

1

What is the correct output if the following array is passed as input?

nums = [-2, 1, 0, 4, -1, 7, 1, 5, -8]

A)

15

B)

17

C)

16

Question 1 of 20 attempted

Try it yourself#

Implement your solution in the following coding playground:

The optimal solution to this problem runs in O(n) time and takes O(1) space.

Python
usercode > main.py
Input #1
%0 node_01 -2 node_11 1 node_21 -3 node_31 4 node_41 -1 node_51 2 node_61 1 node_71 -5 node_81 4
Visualization for Input #1
Maximum Subarray

You might want to go over the Dynamic Programming pattern again.

Solution: Maximum Profit in Job Scheduling

Solution: Maximum Subarray