Leetcode 1262: Greatest Sum Divisible by Three

Input: The input consists of a single integer array 'nums'.

Example: [2, 5, 8, 7, 3]

Constraints:

• 1 <= nums.length <= 4 * 10^4

• 1 <= nums[i] <= 10^4

Output: The output is a single integer representing the maximum sum of any subsequence that is divisible by 3.

Example: 21

Constraints:

• The sum must be divisible by 3.

Goal: Find the maximum possible sum of a subsequence divisible by 3.

Steps:

• 1. Initialize a dynamic programming array 'dp' to store the maximum sum for each remainder modulo 3.

• 2. Iterate through the numbers in 'nums' and update 'dp' based on the current number.

• 3. Return the value in 'dp[0]', which represents the maximum sum divisible by 3.

Goal: The constraints ensure that the array length and values are within a manageable range.

Steps:

• 1 <= nums.length <= 4 * 10^4

• 1 <= nums[i] <= 10^4

Assumptions:

• The input is a valid integer array with values within the given constraints.

• A subsequence is any set of elements in the array, not necessarily contiguous.

• Input: [2, 5, 8, 7, 3]

• Explanation: The sum of the numbers 2, 5, 8, and 7 equals 21, which is divisible by 3. Thus, 21 is the maximum sum.

Approach: Use dynamic programming to track the maximum possible sum for each remainder when divided by 3.

Observations:

• The problem can be reduced to finding the maximum sum for each modulo 3 remainder.

• We can use dynamic programming to keep track of the best possible sums for remainders 0, 1, and 2.

Steps:

• 1. Initialize a dynamic programming array 'dp' of size 3 to keep track of the best sums for each remainder.

• 2. For each number in the array, update the 'dp' array to reflect the best possible sums.

• 3. The maximum sum divisible by 3 will be stored in 'dp[0]'.

Empty Inputs:

• The array is not empty based on the problem constraints.

Large Inputs:

• Ensure that the solution handles arrays with a size up to 40,000 efficiently.

Special Values:

• All numbers in the array could be divisible by 3, or none could be.

Constraints:

• The input array is guaranteed to have at least one element.

int maxSumDivThree(vector<int>& nums) {

    int n = nums.size();
    vector<int> dp(3, 0);

    for(int a : nums)
    for(int i : vector<int>(dp))
    dp[(i + a) % 3] = max(dp[(i + a) % 3], i + a);

    return dp[0];
}

1 : Function Definition

int maxSumDivThree(vector<int>& nums) {

This defines the function `maxSumDivThree`, which takes a vector of integers `nums` and returns the maximum sum divisible by 3 that can be obtained by selecting elements from the list.

2 : Variable Declaration

    int n = nums.size();

This declares an integer `n` to store the size of the input array `nums`.

3 : Vector Initialization

    vector<int> dp(3, 0);

This initializes a vector `dp` of size 3, with all values set to 0. The vector will store the maximum sum possible for each remainder when divided by 3.

4 : Loop (Array Iteration)

    for(int a : nums)

This loop iterates over each element `a` in the input array `nums`.

5 : Loop (Dynamic Programming Update)

    for(int i : vector<int>(dp))

This loop iterates over the current values in the `dp` vector to update the possible sums with the current element `a`.

6 : Dynamic Programming Transition

    dp[(i + a) % 3] = max(dp[(i + a) % 3], i + a);

This updates the `dp` vector by calculating the maximum sum for each possible remainder modulo 3 after adding the current element `a`.

7 : Return Statement

    return dp[0];

This returns the value stored in `dp[0]`, which represents the maximum sum divisible by 3 after processing all elements.

Best Case: O(N), where N is the number of elements in the array.

Average Case: O(N) for each iteration over the array.

Worst Case: O(N), where N is the number of elements in the array.

Description: The time complexity is linear because we iterate over the array once.

Best Case: O(1), since the space usage does not depend on the input size.

Worst Case: O(1), since we only store a fixed-size array (dp) of size 3.

Description: The space complexity is constant because we only need a fixed amount of extra space.

Leetcode 1262: Greatest Sum Divisible by Three

Explore →