SDE - 1

You are given an array of ‘N’ integers and your task is to sort the array using the following operations.
In one operation you can select a sub-array of the array and sort it. The cost of performing such an operation will be the square of the length of the sub-array you are sorting.
You task is to find the minimum cost of sorting the whole array.

For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increasing order.
Strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.

You are given two strings BEGIN and END and an array of strings DICT. Your task is to find the length of the shortest transformation sequence from BEGIN to END such that in every transformation you can change exactly one alphabet and the word formed after each transformation must exist in DICT.