💬 Discord
Sign In
NeetCode #50LC-1800EasyArrays & Hashing
← Back to All Problems

#50 · #1800 · Maximum Ascending Subarray Sum(最大升序子数组和)

📌 Problem Statement & Constraints

Given an array of positive integers nums, return the maximum possible sum of an ascending subarray: a contiguous run of elements where each is strictly greater than the previous. Constraints: 1 <= nums.length <= 100, 1 <= nums[i] <= 100.

💡 Core Algorithmic Approaches

  1. This is the maximum-run template with a sum instead of a length.
  2. Maintain cur, the sum of the current ascending run, and best.
  3. If nums[i] > nums[i-1], extend the run: cur += nums[i]. Otherwise restart the run at nums[i].
  4. Update best after every step. Because all values are positive, restarting is always better than carrying a broken run forward.

💻 Benchmark Python3 Implementation

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        best = cur = nums[0]
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                cur += nums[i]             # extend the ascending run
            else:
                cur = nums[i]              # restart
            best = max(best, cur)
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): two accumulators.

⚠️ Interview Pitfalls & Follow-ups

  • Initialising cur to 0: [5] should return 5, not 0.
  • Using >=: the run must be strictly ascending.
  • Carrying the run across a break: resetting to nums[i] (not 0) is required, since the current element itself starts a new run.
  • Assuming positivity is needed for the greedy: it is what guarantees that a longer run is always at least as good, which is why the simple restart works.