Maximum Ascending Subarray Sum — Easy Problem & Solution

Problem statement

A subarray is ascending when every element is strictly greater than the one before it. A single element is ascending by itself.

Given an array nums, return the largest sum of any ascending contiguous subarray.

Example 1

Input: nums = [10,20,30,5,10,50]
Output: 65
Explanation: The run [5,10,50] sums to 65, beating [10,20,30] at 60.

Example 2

Input: nums = [10,20,30,40,50]
Output: 150
Explanation: The whole array ascends.

Example 3

Input: nums = [12,17,15,13,10,11,12]
Output: 33
Explanation: [10,11,12] sums to 33.

Constraints

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

How to solve Maximum Ascending Subarray Sum

The array splits uniquely into maximal ascending runs, and a best ascending subarray is always a whole run — extending a run only adds positive values. So one pass that sums each run and keeps the maximum is enough.

Approach

1. Start run and best at nums[0].
2. For each later i, if nums[i] > nums[i-1] the run continues, so run += nums[i]; otherwise a new run begins at run = nums[i].
3. Update best = max(best, run) after each step.

Why it works

All values are positive, so within a run the sum is maximised by taking the run entirely. Because runs are maximal and disjoint, taking the best over all of them is the global answer.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Resetting run to 0 loses the element that starts the new run.
• >= would let a flat pair such as [3,3] count as ascending.

Reference solution

Python

from typing import List

def maxAscendingSum(nums: List[int]) -> int:
    best = run = nums[0]
    for i in range(1, len(nums)):
        run = run + nums[i] if nums[i] > nums[i - 1] else nums[i]
        if run > best:
            best = run
    return best

JavaScript

var maxAscendingSum = function(nums) {
    var best = nums[0], run = nums[0];
    for (var i = 1; i < nums.length; i++) {
        run = nums[i] > nums[i - 1] ? run + nums[i] : nums[i];
        if (run > best) best = run;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy