Maximize The Cut Segments

Given an integer n denoting the Length of a line segment. You need to cut the line segment in such a way that the cut length of a line segment each time is either x , y or z. Here x, y, and z are integers.
After performing all the cut operations, your total number of cut segments must be maximum.

Note: if no segment can be cut then return 0.

Examples:

Input: n = 4, x = 2, y = 1, z = 1
Output: 4
Explanation: Total length is 4, and the cut
lengths are 2, 1 and 1. We can make
maximum 4 segments each of length 1.

Input: n = 5, x = 5, y = 3, z = 2
Output: 2
Explanation: Here total length is 5, and
the cut lengths are 5, 3 and 2. We can
make two segments of lengths 3 and 2.

Expected Time Complexity : O(n)
Expected Auxiliary Space: O(n)

Constraints
1 <= n, x, y, z <= 10⁴

Approach 01:

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int maximizeTheCuts(int rodLength, int cutX, int cutY, int cutZ) {
        // Create a memoization array with all values initialized to zero
        std::vector<int> memo(rodLength + 1, 0);

        // Iterate over the rod lengths to fill the memo array
        for (int length = 1; length <= rodLength; ++length) {
            // Initialize current length maximum cuts as -infinity (not possible)
            int maxCuts = INT_MIN;
            
            // Check each cut option and update maxCuts if the cut is possible
            if (length >= cutX) {
                maxCuts = std::max(maxCuts, memo[length - cutX] + 1);
            }
            if (length >= cutY) {
                maxCuts = std::max(maxCuts, memo[length - cutY] + 1);
            }
            if (length >= cutZ) {
                maxCuts = std::max(maxCuts, memo[length - cutZ] + 1);
            }
            
            // Store the maximum cuts possible for this length
            memo[length] = maxCuts;
        }

        // Return the maximum cuts for the full rod length, ensure it's non-negative
        return std::max(memo[rodLength], 0);
    }
};

class Solution:
    def maximizeTheCuts(self, rodLength, cutX, cutY, cutZ):
        # Create a memoization array with all values initialized to zero
        memo = [0] * (rodLength + 1)

        # Iterate over the rod lengths to fill the memo array
        for length in range(1, rodLength + 1):
            # Initialize current length maximum cuts as -infinity (not possible)
            maxCuts = float('-inf')
            
            # Check each cut option and update maxCuts if the cut is possible
            if length >= cutX:
                maxCuts = max(maxCuts, memo[length - cutX] + 1)
            if length >= cutY:
                maxCuts = max(maxCuts, memo[length - cutY] + 1)
            if length >= cutZ:
                maxCuts = max(maxCuts, memo[length - cutZ] + 1)
            
            # Store the maximum cuts possible for this length
            memo[length] = maxCuts

        # Return the maximum cuts for the full rod length, ensure it's non-negative
        return max(memo[rodLength], 0)

Time Complexity

• Loop over Rod Lengths:

  The function iterates over each length from 1 to rodLength, which takes \( O(n) \) time, where \( n \) is the rodLength.

• Check Cut Options:

  For each length, the function checks up to three possible cut options (cutX, cutY, and cutZ), which takes constant time, \( O(1) \).

• Overall Time Complexity:

  The overall time complexity is \( O(n) \), where \( n \) is the rodLength.

Space Complexity

• Memoization Array:

  The function uses a memoization array, memo, of size \( n+1 \) to store the maximum cuts for each rod length. This takes \( O(n) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \) due to the memo array.