We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Ascending Subarray Sum

Number: 1927

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Amazon, tcs

Problem Description

Given an array of positive integers, find the maximum possible sum of a strictly increasing contiguous subarray.

Key Insights

  • A strictly increasing subarray requires each number to be greater than its previous number.
  • Use a single pass to accumulate the current subarray's sum; reset the sum when the current element is not greater than the previous one.
  • Keep track of the maximum sum encountered during the pass.
  • Ensuring to update the maximum after finishing iterating prevents missing the last candidate subarray.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the array because we iterate through the array once. Space Complexity: O(1) - as only a few extra variables are used.

Solution

We iterate through the array while maintaining two variables: currentSum, which accumulates the sum of the current strictly increasing subarray, and maxSum, which records the maximum sum found so far. For each element, if it is greater than the previous element, add it to currentSum. Otherwise, compare currentSum with maxSum, update if necessary, and reset currentSum to the current element. Finally, perform one last comparison after the loop to ensure the maximum sum is captured if the array ends with an ascending sequence. This approach uses a simple linear scan and a few integer variables to keep track of sums.

Code Solutions

# Python solution for Maximum Ascending Subarray Sum

def maxAscendingSum(nums):
    # Initialize both current sum and maximum sum with the first element.
    current_sum = max_sum = nums[0]
    
    # Loop through the array starting from the second element.
    for i in range(1, len(nums)):
        # Check if the current element continues the increasing subarray.
        if nums[i] > nums[i - 1]:
            # Continue the subarray by adding the current element.
            current_sum += nums[i]
        else:
            # Compare and update the maximum sum found so far.
            max_sum = max(max_sum, current_sum)
            # Reset the current sum to the current element.
            current_sum = nums[i]
    
    # Final update for the maximum sum after the loop.
    max_sum = max(max_sum, current_sum)
    return max_sum

# Example usage:
print(maxAscendingSum([10,20,30,5,10,50]))  # Output: 65
← Back to All Questions