একটি গুরুত্বপূর্ন অ্যারের পার্টিশন এ আমরা একটি unique non-decreasing sequence বের করতে পারি। সেটা হল প্রতি সাবঅ্যারে থেকে আমরা greedily next smallest একটি করে উপাদান নিব। যেমন ${[2, 2, 3], [2, 3, 4], [1, 3, 4]}$
থেকে আমরা greedily $2, 2, 3$
অনুক্রুম টি নিব। তো আমরা কাউন্ট করব এই unique sequence গুল থেকে।
কাউন্ট করার জন্য আমরা ডাইনামিক প্রোগ্রামিং অবলম্বন করবো, ধরি $dp[pos][num] =$
প্রথম pos টি উপাদান ব্যবহার করে কতগুলো গুরুত্বপূর্ণ পার্টিশন করা যায় যেখানে sequence টির শেষ উপাদান হল num। যেমন $[3, 1, 2, 4]$
এ $dp[4][4] = 3$
, তা হল ${[3, 1, 2], [4]}, {[3, 1], [2], [4]}, {[3], [1, 2, 4]}$
এই $3$
টি।
তো প্রথমেই একটি $n^4$
সলিউশন লেখা যায় যেখানে $dp[num][pos]$
বের করতে আমরা $pos$
থেকে কিছুটা পিছাবো, $pos'$
এর আগ পর্যন্ত। তারপর এমন সকল $dp[num'][pos']$
এর যোগফল নিব যেন $dp[num'][pos']$
এর একটি sequence এর শেষ উপাদান $num'$
এর পর $[pos'+1.....pos]$
সাবঅ্যারে থেকে next smallest উপাদান num হয়। এক্ষেত্রে খেয়াল রাখতে হবে যেন, $[pos'+1...pos]$
এর ভিতরে $num'$
এর চেয়ে সমান বা বড় উপাদান $num$
ই হয়।
এই সলিউশন টিকে $n^3$
বানানো যায় যদি খেয়াল করো যে একটা নির্দিষ্ট $pos'$
এ আসলে আমরা $num'$
এর একটি রেঞ্জ পাই, তা হল, $[x+1, num]$
, যেখানে $x$
হল $[pos'+1...pos]$
এর ভিতরে $num$
থেকে ছোট সবচেয়ে বড় সংখ্যা । অর্থাৎ ওই রেঞ্জে থাকা সব $num'$
এর জন্যই $dp[num'][pos']$
, $dp[num][pos]$
এর সাথে যোগ হবে। যেহেতু এই রেঞ্জ এর সংখ্যা গুলো আগেই কম্পিউট করা হয়ে গেছে, তাই আমরা cumulative sum এর অ্যারের সাহায্যে $O(1)$
টাইম এ রেঞ্জ সামটি পেতে পারি। আবার একটি জিনিস খেয়াল রাখতে হবে, তা হল আমাদের $pos'$
যাতে এমন হয় যেন $[pos'+1...pos]$
এ কমপক্ষে একটি $num$
থাকে।
এই সলিউশন টিকে $n^2$
বানাতে হলে আরো অবজার্ভ করতে হবে যে $dp[pos][num]$
বের করতে গিয়ে আসলে আমরা যে সকল $dp[pos'][num']$
যোগ করি তারা আসলে শুধু একটি রেঞ্জই না বরং কিছুটা rectangle range এর মত। এক্ষেত্রে ভাল হবে যদি তোমরা হাতে কলমে একটি 2d dp table বানিয়ে দেখ যে $dp[pos][num]$
এ কারা কন্ট্রিবিউট করে। তো আমরা যেটা করব তা হল বের করব আগে এমন $p$
যার জন্য $[p+1...pos]$
এ শুধু মাত্র $p+1$
অবস্থানেই $num$
আছে ($p$
এর চেয়ে বড় $pos'$
গুলো কিন্তু কোন কন্ট্রিবিউট রাখতে পারবে না । এরপর প্রথমেই আমরা সব $dp[pos'][num]$
যোগ করে দিব যেন $pos' <= p$
এবং $num' <= num$
, এটি 2d cumulative sum এর সাহায্যে $O(1)$
এ করা যাবে। এতে কিছু ওভার কাউন্ট হয়েছে, যে যে $pos', num'$
এর জন্য $pos' \leq pos'' \leq pos$
এবং $num' \leq num'' \leq num$
আছে যেন $A[pos''] = num''$
। তো আমরা যেটা করব, একটি $pos$
নির্দিষ্ট করে যখন $num = 1...n$
এর জন্য $dp[pos][num]$
বের করব তখন একটি stack মেইন্টেইন করতে করতে যাব যার ভেতরে $num'', pos''$
গুলো থাকবে, decreasing order এ, এই stack টি আপডেট করার সময়ই আমরা ওভারকাউন্ট করা অংশ গুলি বিয়োগ করে দিব (সেটাও 2d cumulative sum এর মাধ্যমে)। এতে সলিউশনটি $n^2$
হবে।