Krishna’s Divine Partition Complete Solution

This article is part of the Scaler Topics Fortnightly Contest - 23

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

Solution Approach

To ensure an increasing sequence of numbers, the next number must either have more digits than the current number or have the same number of digits but a higher magnitude. Define a state dp[i][len], which represents the maximum number of partitions that can be formed starting from index i, with the previous partition ending at index i-1 and having a length of len.

To transition from one state to the next, we consider three possibilities:

If the current partition can have the same length but be greater than the previous partition, we increment the maximum number of partitions by 1: 1 + dp(i + len, len).
If the current partition has one longer length (which guarantees it will be greater than the previous partition), we increment the maximum number of partitions by 1: 1 + dp(i + len + 1, len + 1).
If the current partition has two longer length, we increment the maximum number of partitions by 1: 1 + dp(i + len + 2, len + 2). This will be important to cover all cases.

The final answer will be the maximum value among these three possibilities. By applying this bottom-up approach.

Time Complexity: $O(N^2)$ Space Complexity: $O(N^2)$