Jobs

Interviews

Discussions

Maximum Ascending Subarray Sum

Easy

Asked by:

13 views

Topics:

ArraysDynamic ProgrammingGreedy Algorithms

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

A subarray is defined as a contiguous sequence of numbers in an array.

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

Try coding it in LeetCode

Maximum Ascending Subarray Sum

Easy

Asked by:

13 views

Topics:

ArraysDynamic ProgrammingGreedy Algorithms

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

A subarray is defined as a contiguous sequence of numbers in an array.

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within the input array? Can they be negative, zero, or only positive?
What should I return if the input array is empty or null?
If there are multiple ascending subarrays with the same maximum sum, should I return any one of them, or is there a specific criterion for choosing one?
What is the maximum possible length of the input array?
Are there any constraints on the time or space complexity of my solution?

Brute Force Solution

Approach

We want to find the biggest sum from a group of numbers that are always increasing. The brute force way is to check every possible group of increasing numbers and keep track of the biggest sum we've seen.

Here's how the algorithm would work step-by-step:

Start at the beginning of the numbers and consider just the first number as a possible group.
Now, consider the first two numbers. If the second number is bigger than the first, they form an increasing group. Calculate their sum.
Next, consider the first three numbers. Check if they form an increasing group (each number must be bigger than the one before it). If they do, calculate their sum.
Keep doing this, each time considering one more number from the beginning, and checking if the group of numbers you're looking at is increasing.
Repeat this whole process starting from the second number in the list, then the third, and so on, so you cover all possible starting points for your increasing groups.
Each time you find an increasing group of numbers, calculate its sum and compare it to the biggest sum you've found so far. If the new sum is bigger, remember it.
After you've checked all possible groups of increasing numbers, the biggest sum you remembered is the answer.

Code Implementation

def max_ascending_subarray_sum_brute_force(numbers):
    maximum_sum = 0

    for start_index in range(len(numbers)):
        current_sum = 0
        # Iterate through all possible subarrays
        for end_index in range(start_index, len(numbers)):
            is_ascending = True
            # Check if the current subarray is ascending
            for check_index in range(start_index + 1, end_index + 1):
                if numbers[check_index] <= numbers[check_index - 1]:
                    is_ascending = False
                    break

            if is_ascending:
                # Sum elements of ascending subarrays
                subarray_sum = 0
                for sum_index in range(start_index, end_index + 1):
                    subarray_sum += numbers[sum_index]

                # Update the maximum sum
                maximum_sum = max(maximum_sum, subarray_sum)

    return maximum_sum

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through the input array (of size n) starting at each possible index. For each starting index, it checks all subsequent subarrays to see if they are strictly ascending. In the worst case, for each of the n starting positions, we may iterate through almost all of the remaining n elements. Therefore, the total number of operations approximates n * n/2, which simplifies to O(n²).

Space Complexity

O(1) – The described brute force approach calculates the sum of each ascending subarray on the fly and compares it to the maximum sum found so far. No additional data structures like temporary lists or hash maps are used to store intermediate subarrays or track visited elements. Only a few variables are needed to keep track of the current subarray's sum and the overall maximum sum. Therefore, the space complexity is constant, independent of the input array's size N.

Optimal Solution

Approach

The fastest way to find the largest sum of an ascending sequence is to avoid recalculating sums repeatedly. We keep track of the current sequence's sum and cleverly update it as we move through the numbers, avoiding redundant calculations.

Here's how the algorithm would work step-by-step:

Start by looking at the first number in the list and consider it as the beginning of a potential ascending sequence.
As you move to the next number, check if it is bigger than the previous number.
If it is bigger, add it to the current sequence's sum and continue building the sequence.
If it is not bigger, the current ascending sequence has ended. Compare the sum of this sequence with the largest sum you've found so far, and remember the larger one.
Start a new ascending sequence from the current number that broke the sequence.
Continue this process until you reach the end of the list.
The largest sum you remembered during the whole process is the answer.

Code Implementation

def max_ascending_subarray_sum(nums):
    maximum_sum_so_far = 0
    current_subarray_sum = 0

    if not nums:
        return 0

    current_subarray_sum = nums[0]
    maximum_sum_so_far = nums[0]

    for i in range(1, len(nums)):
        # Check if the current number extends the ascending subarray
        if nums[i] > nums[i - 1]:

            current_subarray_sum += nums[i]

        else:
            # Update maximum sum if current subarray sum is greater

            maximum_sum_so_far = max(maximum_sum_so_far, current_subarray_sum)
            current_subarray_sum = nums[i]

    # Final check after the loop to account for the last subarray
    maximum_sum_so_far = max(maximum_sum_so_far, current_subarray_sum)

    return maximum_sum_so_far

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n exactly once. In each iteration, it performs a constant amount of work, such as comparing the current element with the previous element and updating the current sum or the maximum sum. Therefore, the time complexity is directly proportional to the number of elements in the array, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm maintains only a constant number of variables: the current ascending subarray sum and the maximum ascending subarray sum encountered so far. No auxiliary data structures like arrays, hash maps, or recursion stacks are created that depend on the input size N (the number of elements in the list). Therefore, the extra space used does not scale with the input size, resulting in constant space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there's no subarray to sum.
Array with a single element	Return the single element's value as it's a trivially ascending subarray.
Array with all elements in strictly ascending order	The entire array is the maximum ascending subarray; sum all elements.
Array with all identical elements	Each element constitutes an ascending subarray of length 1; return the maximum element's value.
Array with a mix of positive and negative numbers, including 0	Negative numbers and zeros will break the ascending subarray, requiring a restart of the sum calculation.
Array with large positive numbers causing potential integer overflow in the sum	Use a data type capable of holding larger sums, such as long or check for overflow and handle appropriately.
Array with descending order	Each element on its own will form a valid subarray; return the largest number.
Very large array to test for algorithm efficiency	The algorithm should have linear time complexity O(n) to scale efficiently.

Null or empty input array

How to Handle:

Return 0 immediately as there's no subarray to sum.

Array with a single element

How to Handle:

Return the single element's value as it's a trivially ascending subarray.

Array with all elements in strictly ascending order

How to Handle:

The entire array is the maximum ascending subarray; sum all elements.

Array with all identical elements

How to Handle:

Each element constitutes an ascending subarray of length 1; return the maximum element's value.

Array with a mix of positive and negative numbers, including 0

How to Handle:

Negative numbers and zeros will break the ascending subarray, requiring a restart of the sum calculation.

Array with large positive numbers causing potential integer overflow in the sum

How to Handle:

Use a data type capable of holding larger sums, such as long or check for overflow and handle appropriately.

Array with descending order

How to Handle:

Each element on its own will form a valid subarray; return the largest number.

Very large array to test for algorithm efficiency

How to Handle:

The algorithm should have linear time complexity O(n) to scale efficiently.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within the input array? Can they be negative, zero, or only positive?
What should I return if the input array is empty or null?
If there are multiple ascending subarrays with the same maximum sum, should I return any one of them, or is there a specific criterion for choosing one?
What is the maximum possible length of the input array?
Are there any constraints on the time or space complexity of my solution?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the numbers and consider just the first number as a possible group.
Now, consider the first two numbers. If the second number is bigger than the first, they form an increasing group. Calculate their sum.
Next, consider the first three numbers. Check if they form an increasing group (each number must be bigger than the one before it). If they do, calculate their sum.
Keep doing this, each time considering one more number from the beginning, and checking if the group of numbers you're looking at is increasing.
Repeat this whole process starting from the second number in the list, then the third, and so on, so you cover all possible starting points for your increasing groups.
Each time you find an increasing group of numbers, calculate its sum and compare it to the biggest sum you've found so far. If the new sum is bigger, remember it.
After you've checked all possible groups of increasing numbers, the biggest sum you remembered is the answer.

Code Implementation

def max_ascending_subarray_sum_brute_force(numbers):
    maximum_sum = 0

    for start_index in range(len(numbers)):
        current_sum = 0
        # Iterate through all possible subarrays
        for end_index in range(start_index, len(numbers)):
            is_ascending = True
            # Check if the current subarray is ascending
            for check_index in range(start_index + 1, end_index + 1):
                if numbers[check_index] <= numbers[check_index - 1]:
                    is_ascending = False
                    break

            if is_ascending:
                # Sum elements of ascending subarrays
                subarray_sum = 0
                for sum_index in range(start_index, end_index + 1):
                    subarray_sum += numbers[sum_index]

                # Update the maximum sum
                maximum_sum = max(maximum_sum, subarray_sum)

    return maximum_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first number in the list and consider it as the beginning of a potential ascending sequence.
As you move to the next number, check if it is bigger than the previous number.
If it is bigger, add it to the current sequence's sum and continue building the sequence.
If it is not bigger, the current ascending sequence has ended. Compare the sum of this sequence with the largest sum you've found so far, and remember the larger one.
Start a new ascending sequence from the current number that broke the sequence.
Continue this process until you reach the end of the list.
The largest sum you remembered during the whole process is the answer.

Code Implementation

def max_ascending_subarray_sum(nums):
    maximum_sum_so_far = 0
    current_subarray_sum = 0

    if not nums:
        return 0

    current_subarray_sum = nums[0]
    maximum_sum_so_far = nums[0]

    for i in range(1, len(nums)):
        # Check if the current number extends the ascending subarray
        if nums[i] > nums[i - 1]:

            current_subarray_sum += nums[i]

        else:
            # Update maximum sum if current subarray sum is greater

            maximum_sum_so_far = max(maximum_sum_so_far, current_subarray_sum)
            current_subarray_sum = nums[i]

    # Final check after the loop to account for the last subarray
    maximum_sum_so_far = max(maximum_sum_so_far, current_subarray_sum)

    return maximum_sum_so_far

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately as there's no subarray to sum.
Array with a single element	Return the single element's value as it's a trivially ascending subarray.
Array with all elements in strictly ascending order	The entire array is the maximum ascending subarray; sum all elements.
Array with all identical elements	Each element constitutes an ascending subarray of length 1; return the maximum element's value.
Array with a mix of positive and negative numbers, including 0	Negative numbers and zeros will break the ascending subarray, requiring a restart of the sum calculation.
Array with large positive numbers causing potential integer overflow in the sum	Use a data type capable of holding larger sums, such as long or check for overflow and handle appropriately.
Array with descending order	Each element on its own will form a valid subarray; return the largest number.
Very large array to test for algorithm efficiency	The algorithm should have linear time complexity O(n) to scale efficiently.

Null or empty input array

How to Handle:

Return 0 immediately as there's no subarray to sum.

Array with a single element

How to Handle:

Return the single element's value as it's a trivially ascending subarray.

Array with all elements in strictly ascending order

How to Handle:

The entire array is the maximum ascending subarray; sum all elements.

Array with all identical elements

How to Handle:

Each element constitutes an ascending subarray of length 1; return the maximum element's value.

Array with a mix of positive and negative numbers, including 0

How to Handle:

Negative numbers and zeros will break the ascending subarray, requiring a restart of the sum calculation.

Array with large positive numbers causing potential integer overflow in the sum

How to Handle:

Use a data type capable of holding larger sums, such as long or check for overflow and handle appropriately.

Array with descending order

How to Handle:

Each element on its own will form a valid subarray; return the largest number.

Very large array to test for algorithm efficiency

How to Handle:

The algorithm should have linear time complexity O(n) to scale efficiently.