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
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program max_ascending_subarray_sum
    implicit none

    integer, parameter :: n = 6
    integer, dimension(n) :: nums
    integer :: i, j, k, l, r, max_sum

    ! Examples
    nums = reshape([10, 20, 30, 5, 10, 50], shape=[n])
    write(*, '(a, i0)') 'Example 1: ', max_ascending_subarray_sum(nums)
    nums = reshape([10, 20, 30, 40, 50], shape=[n])
    write(*, '(a, i0)') 'Example 2: ', max_ascending_subarray_sum(nums)
    nums = reshape([12, 17, 15, 13, 10, 11, 12], shape=[n])
    write(*, '(a, i0)') 'Example 3: ', max_ascending_subarray_sum(nums)

contains

    function max_ascending_subarray_sum(nums) result(max_sum)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: max_sum, current_sum, i, j

        max_sum = 0
        do i = 1, size(nums) - 1
            current_sum = 0
            do j = i, size(nums)
                if (current_sum >= 0 .and. nums(j) > nums(j-1)) then
                    current_sum = current_sum + nums(j)
                else
                    exit
                end if
                max_sum = max(max_sum, current_sum)
            end do
        end do
    end function max_ascending_subarray_sum

end program max_ascending_subarray_sum
❌ Compiled
❌ Executed
❌ Correct 
module max_ascending_subarray_sum
    implicit none
    private
    public :: max_ascending_subarray_sum

contains

    function max_ascending_subarray_sum(nums) result(max_sum)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: max_sum, i, j, sum

        max_sum = 0
        do i = 1, size(nums)
            sum = 0
            do j = i, size(nums)
                if (nums(j) >= nums(j-1)) then
                    sum = sum + nums(j)
                else
                    exit
                end if
            end do
            if (sum > max_sum) then
                max_sum = sum
            end if
        end do
    end function max_ascending_subarray_sum
end module max_ascending_subarray_sum

program test_max_ascending_subarray_sum
    use max_ascending_subarray_sum
    implicit none
    integer :: nums(6)

    nums = [10, 20, 30, 5, 10, 50]
    write (*,*) 'Maximum ascending subarray sum in [10, 20, 30, 5, 10, 50] is', &
        max_ascending_subarray_sum(nums)

    nums = [10, 20, 30, 40, 50]
    write (*,*) 'Maximum ascending subarray sum in [10, 20, 30, 40, 50] is', &
        max_ascending_subarray_sum(nums)

    nums = [12, 17, 15, 13, 10, 11, 12]
    write (*,*) 'Maximum ascending subarray sum in [12, 17, 15, 13, 10, 11, 12] is', &
        max_ascending_subarray_sum(nums)
end program test_max_ascending_subarray_sum
🌐 Data from online sources 
def concatenated_binary(n: int) -> int:
    result = 0
    mod = 1000000007
    for i in range(1, n + 1):
        length = len(bin(i)) - 2
        result = ((result << length) % mod + i) % mod
    return result

The algorithm iterates through all integers from 1 to `n`. For each integer, it first calculates its binary length (i.e. number of bits) using log base 2. This can be done using logarithm internally with floating point representation, followed by flooring and adding 1. In C++, you can use `log2`, in Java you can do `Math.log(i) / Math.log(2)`, and in JavaScript – `Math.log2`.

Then, the result is shifted left by the calculated length (integer arithmetic is mostly used), and the current integer is added to the result. The whole operation is performed under modulo 109 + 7 to prevent overflow. In the end, the result is returned.

🌐 Data from online sources 
#include <bits/stdc++.h>
using namespace std;
int concatenatedBinary(int n) {
    long long result = 0;
    for (int i = 1; i <= n; ++i) {
        int length = log2(i) + 1;
        result = ((result << length) % 1000000007 + i) % 1000000007;
    }
    return result;
}

The algorithm iterates through all integers from 1 to `n`. For each integer, it first calculates its binary length (i.e. number of bits) using log base 2. This can be done using logarithm internally with floating point representation, followed by flooring and adding 1. In C++, you can use `log2`, in Java you can do `Math.log(i) / Math.log(2)`, and in JavaScript – `Math.log2`.

Then, the result is shifted left by the calculated length (integer arithmetic is mostly used), and the current integer is added to the result. The whole operation is performed under modulo 109 + 7 to prevent overflow. In the end, the result is returned.