Problem: Get Maximum Stability

AWS provides a range of servers to meet the deployment needs of its clients. A client wants to choose a set of servers to deploy their application. Each server is associated with an availability factor and a reliability factor.

The client defines the stability of a set of servers as:

Stability = Minimum availability amongst the servers × Sum of reliabilities of all servers.

Given two arrays of integers, availability and reliability, where:

• availability[i] and reliability[i] represent the availability and reliability factors of the i-th server,

find the maximum possible stability of any subset of servers. Since the answer can be large, report the answer modulo 10^9 + 7.

---

Function Description

Function Name: getMaxStability
Parameters:

• int reliability[n]: An array representing server reliability values.
• int availability[n]: An array representing server availability values.

Returns:

• int: The maximum stability among all possible non-empty subsets, modulo 10^9 + 7.

---

Example

Example 1:

Input:
reliability = [1, 2, 2],
availability = [1, 1, 3]

Output:
6

Explanation:

Consider the set of servers where reliability = [1, 2, 2] and availability = [1, 1, 3].

The possible subsets of servers are:

1. Indices {0}: Stability = 1 * 1 = 1
2. Indices {1}: Stability = 1 * 2 = 2
3. Indices {2}: Stability = 3 * 2 = 6
4. Indices {0, 1}: Stability = min(1, 1) * (1 + 2) = 3
5. Indices {0, 2}: Stability = min(1, 3) * (1 + 2) = 3
6. Indices {1, 2}: Stability = min(1, 3) * (2 + 2) = 4
7. Indices {0, 1, 2}: Stability = min(1, 1, 3) * (1 + 2 + 2) = 5

The maximum stability is 6. Return 6 % (10^9 + 7) = 6.

---

Constraints

1. 1 < n ≤ 10^5
2. 1 ≤ reliability[i], availability[i] ≤ 10^6
3. Lengths of reliability and availability are the same.

---

Optimized Approach

Observations:

1. Stability depends on the smallest availability in the subset and the sum of all reliability values.
2. Sorting the servers by availability allows efficient computation:
   • When iterating over servers, treat each server as the minimum availability for subsets including it.
3. Maintain a running sum of reliability values to efficiently compute the sum of reliabilities for subsets.

---

Algorithm

1. Sort: Combine availability and reliability into tuples and sort by availability in descending order.
2. Iterate and Compute Stability:
   • Use a running sum to calculate the total reliability for subsets ending at each server.
   • For each server, calculate the stability as: stability = current availability × running sum of reliability
   • Update the maximum stability found.
3. Return Result Modulo 10^9 + 7: Ensure all calculations are performed under modulo to avoid overflow.

---

Implementation

def getMaxStability(reliability, availability):
    MOD = 10**9 + 7

    # Combine availability and reliability into tuples and sort by descending availability
    servers = sorted(zip(availability, reliability), reverse=True, key=lambda x: x[0])
    
    max_stability = 0
    running_sum = 0

    # Iterate over sorted servers
    for avail, reliab in servers:
        running_sum += reliab
        running_sum %= MOD  # Keep running sum modulo MOD
        
        # Calculate stability for the current subset
        stability = (avail * running_sum) % MOD
        
        # Update maximum stability
        max_stability = max(max_stability, stability)
    
    return max_stability

# Example Usage
reliability = [1, 2, 2]
availability = [1, 1, 3]
print(getMaxStability(reliability, availability))  # Output: 6

---

Complexity Analysis

1. Sorting: O(n log n) for sorting the servers by availability.
2. Single Pass: O(n) for calculating the running sum and stability.
3. Overall Complexity: O(n log n).

---

Example Walkthrough

Input:
reliability = [1, 2, 2]
availability = [1, 1, 3]

• Step 1: Sorting: After sorting: [(3, 2), (1, 2), (1, 1)].
• Step 2: Calculation:
  • For (3, 2): Running sum = 2, Stability = 3 * 2 = 6.
  • For (1, 2): Running sum = 4, Stability = 1 * 4 = 4.
  • For (1, 1): Running sum = 5, Stability = 1 * 5 = 5.

Output:
Maximum stability = 6 % (10^9 + 7) = 6.

---

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.