9

Generate an N-length array having length of non-decreasing subarrays maximized a...

 2 years ago
source link: https://www.geeksforgeeks.org/generate-an-n-length-array-having-length-of-non-decreasing-subarrays-maximized-and-minimum-difference-between-first-and-last-array-elements/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Generate an N-length array having length of non-decreasing subarrays maximized and minimum difference between first and last array elements

  • Last Updated : 30 Jul, 2021

Given an array arr[ ] of size N, the task is to print an N-length array whose sum of lengths of all non-decreasing subarrays is maximum and the difference between the first and last elements is minimum.

Examples:

Input: N = 5, arr = {4, 3, 5, 3, 2}
Output: {3, 4, 5, 2, 3}
Explanation: Difference between the first and last element is minimum, i.e. 3 – 3 = 0, and sum of non-decreasing subarrays is maximum, i.e. 
          1. {3, 4, 5}, length = 3
          2. {2, 3}, length = 2
therefore sum of non-decreasing sub-arrays is 5.

Input: N = 8, arr = {4, 6, 2, 6, 8, 2, 6, 4}
Output: {2, 4, 4, 6, 6, 6, 8, 2}

Approach: The problem can be solved greedily. Follow the steps below to solve the problem:

  • Sort the array arr[ ] in non-decreasing order.
  • Find the index of two consecutive elements with minimum difference, say i and i + 1.
  • Swap arr[0] with arr[i] and arr[N] with arr[i + 1].
  • Swap arr[1 : i – 1] with arr[i + 2 : N – 1].
  • Print the array arr[ ].

Below is the implementation of the above approach:

  • Python3
  • Javascript
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print target array
void printArr(int arr[], int n)
{
// Sort the given array
sort(arr, arr + n);
// Seeking for index of elements with minimum diff.
int minDifference = INT_MAX;
int minIndex = -1;
// Seeking for index
for (int i = 1; i < n; i++) {
if (minDifference
> abs(arr[i] - arr[i - 1])) {
minDifference = abs(arr[i] - arr[i - 1]);
minIndex = i - 1;
}
}
// To store target array
int Arr[n];
Arr[0] = arr[minIndex];
Arr[n - 1] = arr[minIndex + 1];
int pos = 1;
// Copying element
for (int i = minIndex + 2; i < n; i++) {
Arr[pos++] = arr[i];
}
// Copying remaining element
for (int i = 0; i < minIndex; i++) {
Arr[pos++] = arr[i];
}
// Printing target array
for (int i = 0; i < n; i++) {
cout << Arr[i] << " ";
}
}
// Driver Code
int main()
{
// Given Input
int N = 8;
int arr[] = { 4, 6, 2, 6, 8, 2, 6, 4 };
// Function Call
printArr(arr, N);
return 0;
}
Output: 
2 4 4 6 6 6 8 2

Time complexity: O(N*logN)
Auxiliary Space: O(N)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK