Maximum Sum of a Strictly Increasing Subarray
Updated
Problem statement
Given the nonempty integer array nums, return the maximum sum of a nonempty contiguous subarray whose values are strictly increasing from left to right. A single element is a valid increasing subarray.
For every adjacent pair inside the selected subarray, require nums[i]<nums[i+1]. Equality breaks strict growth. You cannot skip positions to form a subsequence, and you cannot cross a decreasing pair.
For this exercise, signed values are allowed. The best choice may discard a negative prefix even within one increasing run. When all values are negative, return the largest value rather than an empty-subarray sum of 0. Find an O(n)-time solution and leave the input unchanged.
Function
maxIncreasingSubarraySum(nums: int[]) → intExamples
Example 1
nums = [7,1,5,8,2,5,6]return = 14The maximal increasing runs are [7], [1,5,8] and [2,5,6]. Their best sums are 7,14,13. The subarray [1,5,8] gives 14. The entire array sums to 34 but is not increasing.
Example 2
nums = [-5,-1,2,3]return = 5The whole array is increasing, but its negative prefix lowers the sum. The nonempty subarray [2,3] has sum 5, larger than the whole-run sum -1.
Constraints
- For this exercise, assume 1 <= nums.length <= 2000.
- For this exercise, assume -1000000 <= nums[i] <= 1000000.
More Morgan Stanley Onsite Interview questions
- Generate Strings of Length at Least ThreeONSITE INTERVIEW · Seen Sep 2026
- Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
- Kth Largest Array ElementONSITE INTERVIEW · Seen Jul 2026
- Run-Length Encode Consecutive Letter RunsONSITE INTERVIEW · Seen Jul 2026
- Maximum Edge Removals for Two TravelersONSITE INTERVIEW · Seen Oct 2025
- Remove K DigitsONSITE INTERVIEW · Seen Oct 2025
- Count Ideal ArraysONSITE INTERVIEW · Seen Aug 2023
- Distinct Palindrome PartitionsONSITE INTERVIEW · Seen Aug 2023
- LFU Cache OperationsONSITE INTERVIEW · Seen Aug 2023
- All-Pairs Shortest PathsOA · ONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Count Subsets With a Target SumSafe Security · ONSITE INTERVIEW
- 0/1 Knapsack with Weight and Volume LimitsGoogle · ONSITE INTERVIEWGoogle interview questions
- Maximum Subarray Sum with One DeletionOracle · ONSITE INTERVIEWOracle interview questions
- Best Time to Buy and Sell Stock IIKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
- Coin ChangeMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Maximum SubarrayUpstart · ONSITE INTERVIEWUpstart interview questions
- Smallest Sufficient TeamExpedia · ONSITE INTERVIEWExpedia interview questions
- Maximum Product SubarrayHartford Financial Services · ONSITE INTERVIEWHartford Financial Services interview questions
- Word BreakMoveworks · ONSITE INTERVIEWMoveworks interview questions
Interview reports that mention this question
Morgan Stanley interview experiences
- Morgan Stanley New Grad Technology Analyst: 2 Experiences
- Morgan Stanley Intern Oldest Loops: 5 Experiences (Part 5 of 5)
- Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
- Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)
- Morgan Stanley Intern Tech Rounds: 5 Experiences (Part 2 of 5)