Maximum Ascending Subarray Sum

Easy
602.

Maximum Ascending Subarray Sum

Maximum Ascending Subarray Sum is an easy coding problem on arrays, asked in Amazon, Infosys and Capgemini interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxAscendingSum = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Ascending Subarray Sum — Problem & Solution

Maximum Ascending Subarray Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays.

Maximum Ascending Subarray Sum is an easy coding problem on arrays, asked in Amazon, Infosys and Capgemini interviews.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon, Infosys, Capgemini
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Maximum Ascending Subarray Sum

  1. Hint 1

    An ascending run ends the moment nums[i] <= nums[i-1] — that is the only place a new run can start.

  2. Hint 2

    Carry the running sum of the current run and the best sum seen so far.

  3. Hint 3

    Reset the running sum to nums[i], not to zero, when the run breaks.

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

Java

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

C++

int maxAscendingSum(vector<int>& nums) {
    int best = nums[0], run = nums[0];
    for (int i = 1; i < (int) nums.size(); i++) {
        run = nums[i] > nums[i - 1] ? run + nums[i] : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays