Xin chào các bạn yêu quý của Learning AI With Losers! Mình là Loser1 đây!

Mùng 6 Ất Tỵ 2025 – ngày đầu tiên trở lại sau kỳ nghỉ Tết, tinh thần vẫn còn phơi phới với bánh chưng và mứt Tết, Hãy cùng khám phá một bài toán thú vị về chuỗi số tăng giảm nghiêm ngặt nào! 🎯Let’s rock and climb! 🏔️

Input: nums = [1,4,3,3,2]
Output: 2
Explanation:
Các mảng con tăng nghiêm ngặt của nums là [1], [2], [3], [3], [4], và [1,4].
Các mảng con giảm nghiêm ngặt của nums là [1], [2], [3], [3], [4], [3,2], và [4,3].
Do đó, chúng ta trả về 2.

Input: nums = [3,3,3,3]
Output: 1
Explanation:
Các mảng con tăng nghiêm ngặt của nums là [3], [3], [3], và [3].
Các mảng con giảm nghiêm ngặt của nums là [3], [3], [3], và [3].
Do đó, chúng ta trả về 1.

Input: nums = [3,2,1]
Output: 3
Explanation:
Các mảng con tăng nghiêm ngặt của nums là [3], [2], và [1].
Các mảng con giảm nghiêm ngặt của nums là [3], [2], [1], [3,2], [2,1], và [3,2,1].
Do đó, chúng ta trả về 3.

🎨 Problem Visualization

Hãy tưởng tượng bạn đang chơi trò chơi leo núi:

Đường đi lên (Strictly Increasing):
🔵 4
🔵 3
🔵 1
↗️ Luôn đi lên, không được đứng yên!

Đường đi xuống (Strictly Decreasing):
🔴 7
🔴 4
🔴 1
↘️ Luôn đi xuống, không được dừng lại!

Đường không hợp lệ:
❌ 3
🔸 3 ❌ 3
↗️ Không được đi ngang!

🔥 First Thoughts & Intuition

Giống như một cuộc phiêu lưu, chúng ta cần tìm:

1. Đường leo núi dài nhất:
   ⛰️ 1 → 4 → 7 → 9
   ↗️ Strictly increasing
2. Đường trượt tuyết dài nhất:
   9 → 6 → 4 → 1 ⛷️
   ↘️ Strictly decreasing
3. So sánh hai đường để tìm max:
   max(đường_leo, đường_trượt)

💡 Approach

1. Mountain Trail Analysis 🏔️

Phân tích đường đi:

🟢 Valid Path
Level 1: 1 → 3 → 5
↗️ ↗️
Luôn tăng!

🔴 Invalid Path
Level 2: 5 → 5 → 7
→ ↗️
Có đi ngang!

2. Double Pass Strategy 🔄

Bước 1: Tìm đường tăng
[1,4,3,3,2]
↗️ Length = 2
[1,4]

Bước 2: Tìm đường giảm
[1,4,3,3,2]
↘️↘️ Length = 3
[4,3,2]

🎯 Example Walkthrough

Case 1: Thử Thách Leo Núi

Input: [1,4,3,3,2]

🌄 Phân Tích:

Tìm đường tăng:
1 → 4 ✅ Length = 2
↗️ Tăng

4 → 3 ❌ Reset!
↘️ Giảm

3 → 3 ❌ Reset!
→ Ngang

3 → 2 ❌ Reset!
↘️ Giảm

Tìm đường giảm:
4 → 3 → 2 ✅ Length = 3
↘️ ↘️
Giảm liên tục!

Case 2: Đỉnh Phẳng

Input: [3,3,3,3]

🏔️ Visualization:
3 → 3 → 3 → 3
→ → →
❌ Không tăng không giảm!
⭐️ Result = 1 (mỗi số đứng một mình)

Case 3: Perfect Descent

Input: [3,2,1]

🎿 Trượt tuyết:
3
↘️
2
↘️
1
✨ Perfect decreasing = 3!

🚀 Implementation

class Solution {
public:
    int maxIncreaseDecreaseSequence(vector<int>& nums) {
        int maxIncrease = 1;  // Max increasing sequence length
        int maxDecrease = 1;  // Max decreasing sequence length
        int currentInc = 1;   // Current increasing count
        int currentDec = 1;   // Current decreasing count
        
        // Find the longest increasing sequence
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i-1]) {  // Strictly increasing
                currentInc++;
                maxIncrease = max(maxIncrease, currentInc);
            } else {
                currentInc = 1;  // Reset when sequence breaks
            }
        }
        
        // Find the longest decreasing sequence
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i-1]) {  // Strictly decreasing
                currentDec++;
                maxDecrease = max(maxDecrease, currentDec);
            } else {
                currentDec = 1;  // Reset when sequence breaks
            }
        }
        
        return max(maxIncrease, maxDecrease);
    }
};

📊 Complexity Analysis

Time Complexity: O(N)

🚶‍♂️ Double Pass Through Array:

Pass 1: Tìm dãy tăng
→ → → → → → →
⏱️ O(N) operations

Pass 2: Tìm dãy giảm
← ← ← ← ← ← ←
⏱️ O(N) operations

Total: O(N + N) = O(N)

Space Complexity: O(1)

🧮 Chỉ cần 4 biến:

• maxIncrease
• maxDecrease
• currentInc
• currentDec

💎 Pro Tips & Tricks

1. Early Detection 🔍

Check điều kiện sớm:
if (nums.size() == 1) return 1;

2. Edge Cases 🎯

• Single element array
• All same elements
• Already sorted array
• Reverse sorted array

3. Performance Tips ⚡

• Avoid extra arrays
• Use direct comparisons
• Reset counters immediately

🌟 Key Insights

1. 📈 Strictly Increasing Rules:

• nums[i] > nums[i-1]
• Không được bằng!
• Reset ngay khi vi phạm

1. 📉 Strictly Decreasing Rules:

• nums[i] < nums[i-1]
• Không được bằng!
• Reset ngay khi vi phạm

1. 🎯 Optimization Strategy:

• Two-pass approach
• In-place counting
• Maximum tracking

Chúc các bạn khởi động sau Tết thật thuận lợi! Hi vọng bài Easy này giúp "warm up" não bộ trước khi chinh phục các thử thách khó hơn! 🎊

Follow mình tại Learning AI with Loser để cập nhật các bài giải Leetcode hàng ngày nhé! 💻✨

CODE EDITOR

#leetcode #leetcodedaily #algorithms #programming #learningwithlosers #backtowork2025 #mariocoding