1

I am trying to make an algorithm that calculates the sum of each maximum element in a subarray not including the first and last elements. The naive approach is obvious but I do not want that.

Here is an example if it is not clear so far:

total = 0
arr = [4, 3, 5, 2, 8, 1]

We start with elements 4 and 5, 3 is the only number so it is the maximum and so the total so far is 3. We then take 4 and 2 and the maximum in between them is 5 so we add it to the total. We take 4 and 8 and 5 is still the maximum so our current total is now 13. Taking 4 and 1 we have a maximum element of 8 so we add 8 to the total which is now 21. Moving to 3 and 2 (since there is no element in between 3 and 5) the maximum is 5 and so we add 5 to the total. Essentially, we will just keep on adding the maximum element in between each possible subarray. How can I do this efficiently?

I already tried the O(n^2) approach clearly that is inefficient and I would like to know a better way to solve this problem. Maybe through a stack or pointers? I am not really sure. I am trying to learn DSA as an advance study for my upcoming dsa course in my university

Improve this question
4
  • Are you sure you meant subsequence and not subarray? Commented May 11, 2024 at 2:01
  • Is it two different terms? Commented May 11, 2024 at 2:05
  • Subsequences do not have to be contiguous. Commented May 11, 2024 at 2:05
  • I meant subarray, my apologies. Commented May 11, 2024 at 2:12

3 Answers 3

Reset to default
1

For each element, we can compute the largest subarray containing it in which it is the maximum element (while not overlapping with subarrays of previous elements, which can happen with adjacent equal elements). With this information, the answer can be computed by multiplying each element with how many subarrays it appears as the maximum in. This can be done in O(n) with two iterations using a monotonic stack.

Example implementation in C++:

#include <span>
#include <vector>
int solve(std::span<int> nums) {
    std::vector<int> leftLarger, stk;
    leftLarger.reserve(nums.size());
    stk.reserve(nums.size());
    for (int i = 0; i < ssize(nums); ++i) {
        while (!stk.empty() && nums[stk.back()] < nums[i]) stk.pop_back();
        leftLarger.push_back(stk.empty() ? 0 : stk.back());
        stk.push_back(i);
    }
    stk.clear();
    int ans = 0;
    for (int i = ssize(nums) - 1; ~i; --i) {
        while (!stk.empty() && nums[stk.back()] <= nums[i]) stk.pop_back();
        ans += nums[i] * ((stk.empty() ? ssize(nums) - 1 : stk.back()) - i) 
                       * (i - leftLarger[i]);
        stk.push_back(i);
    }
    return ans;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

You can try to use the divide-and-conquer approach along with the Kadane's algorithm for finding the maximum subarray sum.

Initialize variables max_so_far and max_ending_here to the minimum possible value. Traverse the array from left to right, but skip the first and last elements.

For each element arr[i]:

a. Update max_ending_here as max(arr[i], max_ending_here + arr[i]).

b. If max_ending_here is not the first or last element in the subarray, update max_so_far as max(max_so_far, max_ending_here).

The final value of max_so_far will be the desired sum.

Time complexity: O(n)

Improve this answer

Comments

0

import sys

def sum_max_subarrays(arr): max_so_far = -sys.maxsize max_ending_here = 0

for i in range(1, len(arr) - 1):
    max_ending_here = max(arr[i], max_ending_here + arr[i])
    if i != 1 and i != len(arr) - 1:
        max_so_far = max(max_so_far, max_ending_here)

return max_so_far

""" Example usage arr = [4, 3, 5, 2, 8, 1] total = sum_max_subarrays(arr) print(f"Total sum of maximum elements in subarrays (excluding first and last): {total}")"""

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.