Maximum Ascending Subarray Sum

Difficulty: Easy | Acceptance: 66.30% | Paid: No Topics: Array

Given an array of positive integers nums, return the maximum sum of an ascending subarray in nums.

A subarray is defined as a contiguous sequence of elements in an array.

A subarray [nums[l], nums[l+1], …, nums[r-1], nums[r]] is ascending if for all i where l <= i < r, nums[i] < nums[i+1]. Note that a subarray of size 1 is ascending.

Table of Contents

• Examples
• Constraints
• Single Pass (Greedy)
• Two Pointers
• Dynamic Programming

Examples

Input: nums = [10,20,30,5,10,50]
Output: 65
Explanation: [5,10,50] is the ascending subarray with the maximum sum of 65.

Input: nums = [10,20,30,40,50]
Output: 150
Explanation: [10,20,30,40,50] is the ascending subarray with the maximum sum of 150.

Input: nums = [12,17,15,3,20,10]
Output: 20
Explanation: [20] is the ascending subarray with the maximum sum of 20.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 100

Single Pass (Greedy)

Intuition Iterate through the array once, maintaining a running sum of the current ascending subarray. When the ascending property breaks, reset the running sum and update the maximum.

Steps

• Initialize max_sum and current_sum to the first element
• Iterate from index 1 to n-1
• If current element > previous element, add to current_sum
• Otherwise, update max_sum and reset current_sum to current element
• After loop, update max_sum one more time
• Return max_sum

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        if not nums:
            return 0
        max_sum = nums[0]
        current_sum = nums[0]
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                current_sum += nums[i]
            else:
                max_sum = max(max_sum, current_sum)
                current_sum = nums[i]
        max_sum = max(max_sum, current_sum)
        return max_sum

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with constant space and single pass

Two Pointers

Intuition Use two pointers to identify each ascending subarray and calculate their sums by iterating through the array boundaries.

Steps

• Initialize max_sum to first element
• Use left pointer at start of current ascending subarray
• Iterate with right pointer
• When ascending property breaks, calculate sum from left to right-1, update max_sum, move left to right
• After loop, calculate final sum and update max_sum
• Return max_sum

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        max_sum = nums[0]
        left = 0
        for right in range(1, n + 1):
            if right == n or nums[right] <= nums[right - 1]:
                current_sum = sum(nums[left:right])
                max_sum = max(max_sum, current_sum)
                left = right
        return max_sum

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Less efficient due to nested loop for sum calculation

Dynamic Programming

Intuition Use DP where dp[i] represents the maximum ascending subarray sum ending at index i, building the solution from previous states.

Steps

• Initialize dp array with same size as nums
• Set dp[0] = nums[0]
• For each i from 1 to n-1:
  • If nums[i] > nums[i-1], dp[i] = dp[i-1] + nums[i]
  • Otherwise, dp[i] = nums[i]
• Return max of dp array

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                dp[i] = dp[i - 1] + nums[i]
            else:
                dp[i] = nums[i]
        return max(dp)

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses extra space for DP array but provides clear state transitions