Join the social network of Tech Nerds, increase skill rank, get work, manage projects...

• # find the longest sub-arraythat all of its elements are less or equalA[i]

• 0
• 0
• 0
• 1
• 0
• 0
• 0
• 415

I have an array `A[1,...,n]` of positive numbers, for example:

``````[1, 2, 5, 3, 7, 2, 8, 4]
``````

I need to build an array `S[1,...,n]` according to the definition:

``````S[i] = max {k|ik <ji :A[j]  A[i] and k  i}
``````

It means to find the longest sub-array `A[i − k,..,i]` that all of its elements are less or equal `A[i]` for each index in the array.

I need to write an algorithm that creates the array S in O(n) using Stack.

For example for the array [1,2,4,3,5] i need to return the array [1,2,3,2,5]

Thank you.

Hi rotemhas,

Following C++ code will solve your problem.

```#include <iostream>
#include <stack>

using namespace std;

void calculate(int arr[], int n)
{
// Create a stack and push index of first element to it
stack<int> st;
st.push(0);

// maximum range value of first element is always 1
int max = 1;
int tmp = 0;
int index = 0;

// Calculate range values for rest of the elements
for ( int i = 1; i < n; i++) {
// Pop elements from stack while stack is not empty and top of
// stack is smaller than price[i]
while (!st.empty() && arr[st.top()] < arr[i])
st.pop();

// If stack becomes empty, then arr[i] is greater than all elements
// on left of it, i.e., arr[0], arr[1],..arr[i-1].  Else arr[i]
// is greater than elements after top of stack
tmp = (st.empty())?(i+1):(i-st.top());

if(tmp > max) {  // to maintain a record for longest range upto i-th element
max = tmp;
index = i;
}

// Push this element to stack
st.push(i);
}
int startIndex = index-max+1; // startIndex will point to the starting index of subarray
int limitIndex = index;       // limitIndex will point to last index of sub array according to the problem.

//to print the range
cout << "The final subarray will be  : ";
for ( int i = startIndex; i <= limitIndex; i++)
cout << arr[i] << " ";
cout << endl;

return;
}

int main()
{
int n;
cout << "Enter the size of array : ";
cin >> n;
int arr[n];
cout << "Enter the elements of array : ";
for ( int i = 0; i < n; i++)
cin >> arr[i];

calculate(arr,n);

return 0;
}
```

Sample Inputs and Outputs

```Enter the size of array : 7
Enter the elements of array : 100 80 60 70 60 75 85
The final subarray will be  : 80 60 70 60 75 85

Enter the size of array : 6
Enter the elements of array : 1 1 1 1 1 1
The final subarray will be  : 1

Enter the size of array : 5
Enter the elements of array : 1 2 3 4 5
The final subarray will be  : 1 2 3 4 5

Enter the size of array : 8
Enter the elements of array : 1 2 5 3 7 2 8 4
The final subarray will be  : 1 2 5 3 7 2 8
```

Thanks for posting your problem on Findnerd :)

OR
OR
Register

OR
Fill out the form below and instructions to reset your password will be emailed to you:

• Hire
• Post Projects

### Post Projects

• All at 0 Cost ....
• Post Tech Job
• Select Best Bidder
• Track the Project
• Approve Work and Pay safely
• Browse Nerds
• Work
• Find Projects Find Projects
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
View more...
View less...
• Manage
• Company Company

### Manage Company

• All at 0 Cost ....
• Manage Company and Employee Profiles
• Company wide Employee Productivity Reports
• Knowledge Sharing and Collaboration Tools
• Get Sales Lead and Bid for Tech Projects
• Send Invoices and Receive Payment Safely
• Learn
• Nerd Digest Nerd Digest
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
View more...
View less...
• Tech Q & A Tech Q & A
• UI Design and UX
• Software Engineering
View more...
View less...
• Marketing
• General
View more...
View less...