Teaching Kids Programming – Maximum Ascending Subarray Sum (Greedy Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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, 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

Greedy Math Solution/Algorithm to Compute the Maximum Ascending Subarray Sum

Given the numbers are positive, we can apply greedy solution. If the numbers contain negative numbers, the greedy strategy won’t work. For example:

[-10, -5, 100], with the greedy, we take all, since it is all increasing, but the optimal solution is to take 100 only.

The solution is to take next increasing number in the sublist as it is positive. And reset/restart if it is not increasing anymore:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        n = len(nums)
        if not n:
            return 0
        ans = cur = nums[0]        
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                cur += nums[i]
            else:
                cur = nums[i]
            ans = max(cur, ans)
        return ans

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        n = len(nums)
        if not n:
            return 0
        ans = cur = nums[0]        
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                cur += nums[i]
            else:
                cur = nums[i]
            ans = max(cur, ans)
        return ans

The Time Complexity is O(N) where N is the number of elements in the array. The space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
a WordPress rating system

429 words
Last Post: Teaching Kids Programming – Finding Path Sum in Binary Tree via Breadth First Search Algorithm (and Iterative DFS)