Total Rod Length: 7 units
|--------------------------------------|

Available Segment Lengths:
Segment 1: |-----|  (5 units)
Segment 2: |--|     (2 units)
Segment 3: |--|     (2 units)

Goal: Cut the rod into maximum number of segments using only these lengths.

|--------------------------------------|
|--|  |--|  |-----|
 2    2     3    = 7 units total

Total segments used: 3

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int max_segments(int remainingLength, int segment1, int segment2, int segment3) {
    // Base case: if the rod is completely used up
    if (remainingLength == 0) return 0;
    
    // Base case: if we've cut too much (invalid case)
    if (remainingLength < 0) return INT_MIN;
    
    // Recursive cases: try cutting with each segment length
    int cutWithSegment1 = max_segments(remainingLength - segment1, segment1, segment2, segment3) + 1;
    int cutWithSegment2 = max_segments(remainingLength - segment2, segment1, segment2, segment3) + 1;
    int cutWithSegment3 = max_segments(remainingLength - segment3, segment1, segment2, segment3) + 1;
    
    // Return the maximum of the three possibilities
    int maxCuts = max(cutWithSegment1, max(cutWithSegment2, cutWithSegment3));
    return maxCuts;
}

int main() {
    int totalRodLength = 7;
    int segment1Length = 5;
    int segment2Length = 2;
    int segment3Length = 2;
    
    int maxSegments = max_segments(totalRodLength, segment1Length, segment2Length, segment3Length);
    
    // If the result is negative, it means no valid solution was found
    if (maxSegments < 0) {
        maxSegments = 0;
    }
    
    cout << "Maximum number of segments: " << maxSegments << " ";
    return 0;
}

                          max_segments(7, 5, 2, 2)
               /                     |                     \
    max_seg(2,5,2,2)         max_seg(5,5,2,2)         max_seg(5,5,2,2)
    /         |     \         /      |      \         /      |      \
max(-3) max(0)  max(0)   max(0)  max(3)  max(3)   max(0)  max(3)  max(3)