SDE - 1

You have been given an array 'PRICES' consisting of 'N' integers where PRICES[i] denotes the price of a given stock on the i-th day. You are also given an integer 'K' denoting the number of possible transactions you can make.

Your task is to find the maximum profit in at most K transactions. A valid transaction involves buying a stock and then selling it.

Note

You can’t engage in multiple transactions simultaneously, i.e. you must sell the stock before rebuying it.

For Example

Input: N = 6 , PRICES = [3, 2, 6, 5, 0, 3] and K = 2.
Output: 7

Explanation : The optimal way to get maximum profit is to buy the stock on day 2(price = 2) and sell it on day 3(price = 6) and rebuy it on day 5(price = 0) and sell it on day 6(price = 3). The maximum profit will be (6 - 2) + (3 - 0) = 7.

You are given a matrix ‘ARR’ with ‘N’ rows and ‘M’ columns. Your task is to find the maximum sum rectangle in the matrix.

Maximum sum rectangle is a rectangle with the maximum value for the sum of integers present within its boundary, considering all the rectangles that can be formed from the elements of that matrix.

For Example

Consider following matrix:

The rectangle (1,1) to (3,3) is the rectangle with the maximum sum, i.e. 29.

You have been given a Snake and Ladder Board with 'N' rows and 'N' columns with the numbers written from 1 to (N*N) starting from the bottom left of the board, and alternating direction each row.

For example

For a (6 x 6) board, the numbers are written as follows:

You start from square 1 of the board (which is always in the last row and first column). On each square say 'X', you can throw a dice which can have six outcomes and you have total control over the outcome of dice throw and you want to find out the minimum number of throws required to reach the last cell.
Some of the squares contain Snakes and Ladders, and these are possibilities of a throw at square 'X':
You choose a destination square 'S' with number 'X+1', 'X+2', 'X+3', 'X+4', 'X+5', or 'X+6', provided this number is <= N*N.
If 'S' has a snake or ladder, you move to the destination of that snake or ladder.  Otherwise, you move to S.
A board square on row 'i' and column 'j' has a "Snake or Ladder" if board[i][j] != -1. The destination of that snake or ladder is board[i][j].

Note :

You can only take a snake or ladder at most once per move: if the destination to a snake or ladder is the start of another snake or ladder, you do not continue moving - you have to ignore the snake or ladder present on that square.

For example, if the board is:
-1 1 -1
-1 -1 9
-1 4 -1
Let's say on the first move your destination square is 2  [at row 2, column 1], then you finish your first move at 4 [at row 1, column 2] because you do not continue moving to 9 [at row 0, column 0] by taking the ladder from 4.

A square can also have a Snake or Ladder which will end at the same cell.
For example, if the board is:
-1 3 -1
-1 5 -1
-1 -1 9
Here we can see Snake/Ladder on square 5 [at row 1, column 1] will end on the same square 5.

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.

For example:

[1, 2, 3, 4] is a strictly increasing array, while [2, 1, 4, 3] is not.

You have been given a MATRIX of non-negative integers of size N x M where 'N' and 'M' denote the number of rows and columns, respectively.

Your task is to find the length of the longest increasing path when you can move to either four directions: left, right, up or down from each cell. Moving diagonally or outside the boundary is not allowed.

Note: A sequence of integers is said to form an increasing path in the matrix if the integers when traversed along the allowed directions can be arranged in strictly increasing order. The length of an increasing path is the number of integers in that path.

For example :

3 2 2
5 6 6
9 5 11 

In the given matrix, 3 →  5 →  6 and 3 →  5 →  9 form increasing paths of length 3 each.

You have been given a sorted array/list 'arr' consisting of ‘n’ elements. You are also given an integer ‘k’.

Now the array is rotated at some pivot point unknown to you.

For example, if 'arr' = [ 1, 3, 5, 7, 8], then after rotating 'arr' at index 3, the array will be 'arr' = [7, 8, 1, 3, 5].

Now, your task is to find the index at which ‘k’ is present in 'arr'.

Note :

1. If ‘k’ is not present in 'arr', then print -1.
2. There are no duplicate elements present in 'arr'. 
3. 'arr' can be rotated only in the right direction.

Example:

Input: 'arr' = [12, 15, 18, 2, 4] , 'k' = 2

Output: 3

Explanation:
If 'arr' = [12, 15, 18, 2, 4] and 'k' = 2, then the position at which 'k' is present in the array is 3 (0-indexed).