Cisco OA-8 2022

Problem Description

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Constraints:

• 1 < nums.length <= 10^5
• -10^4 < nums[i] <= 10^4

Test Case 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 of 6.

Test Case Example 2

Input:

nums = [1]

Output:

1

Explanation:

• The subarray [1] has the largest sum of 1.

Test Case Example 3

Input:

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

Output:

23

Explanation:

• The subarray [5, 4, -1, 7, 8] has the largest sum of 23.