Wednesday, June 29, 2022
HomeSoftware DevelopmentMaximize worth obtained in Array by leaping to the following consecutive higher

# Maximize worth obtained in Array by leaping to the following consecutive higher

Given an array arr[] of size N, the task is to find the maximum value that can be obtained by following the below conditions:

• Select any element (say k) from the array and increase all other elements by 1.
• In the next step, jump only to the index with a value k+1.
• In the end, you are at the maximum value.

Examples:

Input: N = 4, arr[] ={1, 2, 1, 3}
Output: 3
Explanation: If started from index 0 with a height of 1 unit, then,
the new value of array will be [1, 3, 2, 4].
Then jump to the index with (1+1 = 2) ie 2nd index,
The updated values are [2, 4, 2, 5]. Cannot be at the maximum value at end
The first chosen value was 3 at index 3.
The updated values are [2, 3, 2, 3]. Max achieved -3. Hence ans = 3;

Input: N = 4, arr[]={1, 2, 3, 3}
Output: 4

Approach: The problem can be solved based on the following observation:

On observation, we can realize that for reaching maximum height we have two options

• Directly selecting the maximum heighted podium initially available.
• Choosing all the elements (say total y) with same value (say x). So highest number that can be reached is (x + y – 1).

Follow the below steps to solve the problem:

• Sort the array in increasing order.
• Seek for the span of the same value elements and get the maximum value that can be achieved from that span using the above idea.
• Perform this for all available spans and store the maximum.
• Return the maximum as the required answer.

Below is the implementation of the above approach.

## C++

 ` `  `#include ` `using` `namespace` `std;` ` `  `int` `maxVal(``int` `n, ``int` `a[])` `{` `    ` `    ` `    ``sort(a, a + n);` `    ``int` `ans = 0, span = 0;` `    ``for` `(``int` `i = 1; i < n; i++) {` ` `  `        ` `        ``if` `(a[i - 1] == a[i]) {` `            ``span++;` `        ``}` `        ``else` `{` ` `  `            ` `            ` `            ``ans = max(ans, a[i - 1] + span);` `            ``span = 0;` `        ``}` `    ``}` `    ``ans = max(ans, a[n - 1] + span);` `    ``ans = max(ans, a[n - 1]);` ` `  `    ` `    ` `    ``return` `ans;` `}` ` `  `int` `main()` `{` `    ``int` `N = 4;` `    ``int` `arr[] = { 1, 2, 1, 3 };` ` `  `    ` `    ``cout << maxVal(N, arr) << endl;` `    ``return` `0;` `}`

Time Complexity: O(N*logN)
Auxiliary Space: O(1)

RELATED ARTICLES