1800. Maximum Ascending Subarray Sum

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 [numsl, numsl+1, ..., numsr-1, numsr] is ascending if for all i where l <= i < r, numsi < numsi+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 01:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxAscendingSum(vector<int>& nums) {
        int currentSum = nums[0];
        int maxSum = INT_MIN;
        int arraySize = nums.size();

        for (int i = 1; i < arraySize; i++) {
            if (nums[i] > nums[i - 1]) {
                currentSum += nums[i];
            } else {
                maxSum = max(maxSum, currentSum);
                currentSum = nums[i];
            }
        }
        
        return max(maxSum, currentSum);
    }
};

from typing import List

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        currentSum = nums[0]
        maxSum = float('-inf')
        arraySize = len(nums)

        for i in range(1, arraySize):
            if nums[i] > nums[i - 1]:
                currentSum += nums[i]
            else:
                maxSum = max(maxSum, currentSum)
                currentSum = nums[i]

        return max(maxSum, currentSum)

Time Complexity:

• Single Pass:

  We iterate through the array once, processing each element in \( O(1) \) time.

• Overall Time Complexity:

  \( O(N) \), where \( N \) is the size of the input array.

Space Complexity:

• Auxiliary Space:

  We use only a few integer variables (currentSum, maxSum, arraySize), all of which take \( O(1) \) space.

• Overall Space Complexity:

  \( O(1) \).