1800. Maximum Ascending Subarray Sum Solution

The problem

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

A subarray is defined as a contiguous sequence of numbers 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.

Example 1:

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

Example 2:

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.

Example 3:

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

Constraints:

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

Approach overview

Problem Overview: You are given an integer array and need to compute the maximum possible sum of a contiguous subarray where each element is strictly greater than the previous one. The subarray must remain strictly ascending from left to right, and the goal is to track the highest sum among all such segments.

This problem falls under common array traversal patterns. The key challenge is recognizing when an ascending streak continues and when it breaks so you can reset the running total.

Approach 1: Single Pass with Current Sum Tracker (O(n) time, O(1) space)

Scan the array once while maintaining two variables: currentSum for the sum of the current ascending segment and maxSum for the best result seen so far. Start with the first element as the current sum. While iterating, check if nums[i] > nums[i-1]. If true, the ascending order continues, so add the element to currentSum. If not, the ascending streak breaks and you reset currentSum to the current element. After each step, update maxSum = max(maxSum, currentSum). This works because every ascending segment is processed exactly once, and each element contributes to at most one running sum.

The insight is that an ascending subarray cannot extend across a non-increasing boundary. Instead of checking every possible subarray, you treat each increasing run as a single candidate segment. The algorithm performs a single linear pass through the array, giving O(n) time complexity and constant O(1) space.

Approach 2: Divide and Conquer Strategy (O(n log n) time, O(log n) space)

This approach recursively splits the array into two halves, similar to classic divide-and-conquer patterns. For each segment, compute three values: the best ascending subarray entirely in the left half, the best entirely in the right half, and a potential ascending subarray that crosses the midpoint. The crossing case is valid only if the boundary elements maintain the strictly increasing condition.

During the merge step, you combine results from both halves while checking whether the rightmost value of the left segment is smaller than the leftmost value of the right segment. If so, the ascending sequence can extend across the midpoint, and you compute the combined sum. Recursion depth contributes O(log n) stack space, and each level processes O(n) work, leading to O(n log n) total time.

Recommended for interviews: The single-pass running sum approach is what interviewers expect. It demonstrates strong understanding of array traversal and state tracking while achieving optimal O(n) time and O(1) space. The divide-and-conquer version is academically interesting and shows familiarity with recursive decomposition, but it introduces unnecessary overhead for this problem.

Approach 1: Using a Single Pass with Current Sum Tracker

This approach uses a single pass over the array while maintaining a current sum of an ascending subarray. As we iterate over the array, we check if the current number is greater than the previous one to have an ascending subarray.

If the current number is greater, add it to the current sum; otherwise, check if the current sum is greater than the maximum sum found so far and reset the current sum to the current number.

Finally, ensure to compare the last current sum with the maximum sum after the loop to cover the case where the array ends with an ascending subarray.

Python

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

JavaScript

function maxAscendingSum(nums) {
    let maxSum = nums[0], currentSum = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            currentSum += nums[i];
        } else {
            currentSum = nums[i];
        }
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

The solution initializes max_sum and current_sum with the first element. As it iterates, it adds the current element to current_sum if it's greater than the previous one; otherwise, it resets current_sum. It updates max_sum accordingly.

Complexity

Time Complexity: O(n), where n is the length of the array, because the solution iterates over the array once.
Space Complexity: O(1), as we only use a constant amount of extra space for variables.

Try this approach in the editor

Approach 2: Divide and Conquer Strategy

This approach utilizes a divide and conquer technique. The concept involves dividing the array into two halves, recursively finding the maximum ascending subarray sum in each half, and considering the possibility of maximum ascending subarray crossing the midpoint.

We combine these results to derive the solution.

Java

public class MaxAscendingSum {
    private int maxCrossingSum(int[] nums, int left, int mid, int right) {
        int leftSum = nums[mid], rightSum = nums[mid + 1];
        int tempSum = leftSum;

        for (int i = mid - 1; i >= left && nums[i] < nums[i + 1]; i--) {
            tempSum += nums[i];
            leftSum = Math.max(leftSum, tempSum);
        }

        tempSum = rightSum;
        for (int i = mid + 2; i <= right && nums[i] > nums[i - 1]; i++) {
            tempSum += nums[i];
            rightSum = Math.max(rightSum, tempSum);
        }

        return Math.max(Math.max(leftSum, rightSum), leftSum + rightSum);
    }

    private int maxAscendingSumHelper(int[] nums, int left, int right) {
        if (left == right) return nums[left];
        int mid = left + (right - left) / 2;
        return Math.max(Math.max(maxAscendingSumHelper(nums, left, mid),
                                 maxAscendingSumHelper(nums, mid + 1, right)),
                        maxCrossingSum(nums, left, mid, right));
    }

    public int maxAscendingSum(int[] nums) {
        return maxAscendingSumHelper(nums, 0, nums.length - 1);
    }
}

C++

#include <vector>
#include <algorithm>

int maxCrossingSum(const std::vector<int>& nums, int left, int mid, int right) {
    int leftSum = 0, maxLeftSum = nums[mid];
    for (int i = mid; i >= left && nums[i] < nums[i + 1]; --i) {
        leftSum += nums[i];
        maxLeftSum = std::max(maxLeftSum, leftSum);
    }

    int rightSum = 0, maxRightSum = nums[mid + 1];
    for (int i = mid + 1; i <= right && nums[i] > nums[i - 1]; ++i) {
        rightSum += nums[i];
        maxRightSum = std::max(maxRightSum, rightSum);
    }

    return std::max({maxLeftSum, maxRightSum, leftSum + rightSum});
}

int maxAscendingSumHelper(const std::vector<int>& nums, int left, int right) {
    if (left == right) return nums[left];
    int mid = left + (right - left) / 2;
    return std::max({maxAscendingSumHelper(nums, left, mid),
                    maxAscendingSumHelper(nums, mid + 1, right),
                    maxCrossingSum(nums, left, mid, right)});
}

int maxAscendingSum(std::vector<int>& nums) {
    return maxAscendingSumHelper(nums, 0, nums.size() - 1);
}

This Java solution implements a divide and conquer method, similar to merge sort. It recursively calculates the maximum sum in the left, right, and crossing subarrays, combining them to find the maximum possible ascending subarray sum.

Complexity

Time Complexity: O(n log n), stemming from the recursive divisions and calculations similar to merge sort.
Space Complexity: O(log n), due to the recursion stack.

Try this approach in the editor

Approach 3: Direct Simulation

We use a variable t to record the current sum of the ascending subarray, and a variable ans to record the maximum sum of the ascending subarray.

Traverse the array nums:

If the current element is the first element of the array, or the current element is greater than the previous one, then add the current element to the sum of the current ascending subarray, i.e., t = t + nums[i], and update the maximum sum of the ascending subarray ans = max(ans, t). Otherwise, the current element does not satisfy the condition of the ascending subarray, so reset the sum t of the current ascending subarray to the current element, i.e., t = nums[i].

After the traversal, return the maximum sum of the ascending subarray ans.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

TypeScript

function maxAscendingSum(nums: number[]): number {
    const n = nums.length;
    let res = nums[0];
    let sum = nums[0];
    for (let i = 1; i < n; i++) {
        if (nums[i] <= nums[i - 1]) {
            res = Math.max(res, sum);
            sum = 0;
        }
        sum += nums[i];
    }
    return Math.max(res, sum);
}

#define max(a, b) (((a) > (b)) ? (a) : (b))

int maxAscendingSum(int* nums, int numsSize) {
    int res = nums[0];
    int sum = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i - 1] >= nums[i]) {
            res = max(res, sum);
            sum = 0;
        }
        sum += nums[i];
    }
    return max(res, sum);
}

func maxAscendingSum(nums []int) int {
	ans, t := 0, 0
	for i, v := range nums {
		if i == 0 || v > nums[i-1] {
			t += v
			if ans < t {
				ans = t
			}
		} else {
			t = v
		}
	}
	return ans
}

Rust

impl Solution {
    pub fn max_ascending_sum(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = nums[0];
        let mut sum = nums[0];
        for i in 1..n {
            if nums[i - 1] >= nums[i] {
                res = res.max(sum);
                sum = 0;
            }
            sum += nums[i];
        }
        res.max(sum)
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using a Single Pass with Current Sum Tracker	Time Complexity: O(n), where n is the length of the array, because the solution iterates over the array once. Space Complexity: O(1), as we only use a constant amount of extra space for variables.
Divide and Conquer Strategy	Time Complexity: O(n log n), stemming from the recursive divisions and calculations similar to merge sort. Space Complexity: O(log n), due to the recursion stack.
Direct Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Single Pass with Current Sum Tracker	O(n)	O(1)	Best general solution. Linear scan with constant memory, ideal for interviews and production.
Divide and Conquer Strategy	O(n log n)	O(log n)	Useful for practicing recursive array decomposition or divide-and-conquer patterns.

Frequently asked questions

Is Maximum Ascending Subarray Sum easy or hard?

Maximum Ascending Subarray Sum is classified as an Easy problem on LeetCode. The challenge focuses on recognizing ascending segments and maintaining a running sum, which makes it a good introduction to array traversal and subarray problems.

Maximum Ascending Subarray Sum Python/Java solution

The common implementation in Python or Java performs a linear scan with two variables: currentSum and maxSum. Compare each element with the previous one to determine whether the ascending sequence continues or resets. This implementation runs in O(n) time and uses constant space.

How to solve Maximum Ascending Subarray Sum in O(n)?

Iterate through the array while maintaining a running sum for the current ascending segment. If nums[i] > nums[i-1], add nums[i] to the current sum; otherwise reset the sum to nums[i]. Track the maximum value of this running sum during the traversal. This single-pass strategy guarantees O(n) time.

What is the best approach for Maximum Ascending Subarray Sum?

The optimal approach uses a single pass through the array while tracking the current ascending segment sum. If the current number is greater than the previous one, add it to the running sum; otherwise reset the sum. This method runs in O(n) time with O(1) space and is the solution typically expected in interviews.

Is Maximum Ascending Subarray Sum asked at Google/Amazon/Meta?

Problems based on array traversal and subarray patterns frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the underlying concept of tracking increasing segments or subarray sums is commonly tested.

What data structure is used in Maximum Ascending Subarray Sum?

The problem primarily uses a basic array traversal technique. No advanced data structures are required—just variables to track the current ascending subarray sum and the maximum sum found so far.

What is the time complexity of Maximum Ascending Subarray Sum?

The optimal algorithm runs in O(n) time because it scans the array exactly once. Each element is processed with a constant number of comparisons and additions. Space complexity is O(1) since only a few variables are used to track the running and maximum sums.

Maximum Ascending Subarray Sum solution and explanation

The problem

Approach overview

Approach 1: Using a Single Pass with Current Sum Tracker

Approach 2: Divide and Conquer Strategy

Approach 3: Direct Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Ascending Subarray Sum solution and explanation

The problem

Approach overview

Approach 1: Using a Single Pass with Current Sum Tracker

Approach 2: Divide and Conquer Strategy

Approach 3: Direct Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems