In the context of maximizing earnings by adding at most $$$(m)$$$ negative elements, the optimal solution involves sorting the array in non-decreasing order and summing up the first at most $$$m$$$ (possibly zero) negative numbers.

Time complexity: O($$$(nlogn)$$$) where $$$n$$$ is the number of TV Sets we have Space complexity: O(1)

n, m = map(int, input().split())
tvSets = list(map(int, input().split()))    
tvSets.sort()
ans = 0
# iterate over tv sets m time
for i in range(m):
    # sum up negative numbers only
    if tvSets[i] < 0:
        ans += tvSets[i]
    else:
        break
print(-ans)

We can delete all zeros from the array, and it won't affect the answer.

The maximum sum is Σ (from i=1 to n) |ai|. The minimum number of operations we should do is the number of continuous subsequences with negative values of elements.

Total complexity: O(n) Space complexity: O(1)

T = int(input())

for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    
    total_sum = 0
    negative_subsequences = 0
    is_negative_subsequence = False
    
    for element in a:
        total_sum += abs(element)
        
        if element < 0 and not is_negative_subsequence:
            is_negative_subsequence = True
            negative_subsequences += 1
        
        if element > 0:
            is_negative_subsequence = False
 
    print(total_sum, negative_subsequences)

Let’s calculate the maximum number of problems we can take, and the answer will be n subtracted by that count.

An arrangement that always minimizes the absolute difference between adjacent pairs is the array in sorted order. What we notice, is that if the array is sorted, we will always take a subarray (all taken elements will be consecutive).

So, the problem converts to finding the largest element subarray for which ai — ai — 1 <= k. It’s easy to see that all the subarrays are totally different (don’t share any intersection of elements), thus, we can maintain a count variable of the current number of elements in the current subarray, and iterate through array elements from left to right. If we currently are at i and ai — ai — 1 > k then we just set the count to 1 since we know a new subarray starts, otherwise, we just increase our count by 1. The answer will be n subtracted by the largest value that our count has achieved.

Time complexity: O(nlogn) Space complexity: O(1)

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    a.sort()
    
    cnt = 1
    ans = 1
    
    for i in range(1, n):
        if a[i] - a[i - 1] > k:
            cnt = 1
        else:
            cnt += 1
        ans = max(ans, cnt)
    
    print(n - ans)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

Iterates through the array, starting from the second index, comparing each element to its leftmost minimum and right neighbor. If at any point the current element is greater than both its leftmost minimum elements and right neighbors, the answer is 'NO', indicating the absence of a valid valley. Otherwise, the answer remains 'YES' and we will update the leftmost minimum element.

Time complexity: O(n), n is length of the array Space complexity: O(1)

# iterating over the test cases
 for _ in range(int(input())):
    n = int(input())
    nums = list(map(int, input().split()))
    indx = 1
    ans = 'YES'
    leftMin = nums[0]
    # iterate over the array starting from the second index
    while indx <= n - 2:
        # compare current element with leftmost minimum elements and right neighbors
        if leftMin < nums[indx] > nums[indx + 1]:
            ans = 'NO'
            break
        leftMin = min(leftMin, nums[indx])
        indx += 1
    print(ans)

The problem can be efficiently solved using the two-pointer technique. Let's denote the first pointer as left (l) and the second pointer as right (r). For each position of left, we move the right end right until, on the substring s[l, l+1, ..., r], it is possible to make no more than k swaps to transform this substring into a beautiful one. We then update the answer with the length of this substring and move left to the right.

Time complexity: O(n) Space complexity: O(1)

n, k = map(int, input().split())
s = input()

left = 0
b = 0
max_length = 1

# Handling 'b' characters
for right in range(n):
    if s[right] == 'b':
        b += 1

    # Move the left pointer until it's possible to make no more than k swaps
    while b > k:
        if s[left] == 'b':
            b -= 1
        left += 1

    max_length = max(max_length, right - left + 1)

# Reset pointers and handle 'a' characters
left = 0
a = 0

for right in range(n):
    if s[right] == 'a':
        a += 1

    # Move the left pointer until it's possible to make no more than k swaps
    while a > k:
        if s[left] == 'a':
            a -= 1
        left += 1

    max_length = max(max_length, right - left + 1)

print(max_length)