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

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

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

GD Star Rating
a WordPress rating system

Source: Internet

We are offering free coding tuts

X