รับอาร์เรย์ arr[] ที่มีจำนวนเต็มบวก เป้าหมายคือการหาจำนวนของอาร์เรย์ย่อยที่มีความยาวอย่างน้อย 1 ซึ่งไม่เพิ่มขึ้น ถ้า arr[]={1,3,2} อาร์เรย์ย่อยจะเป็น {1}, {2}, {3}, {3,2} นับเป็น 4
ตัวอย่าง
อินพุต
arr[] = {5,4,5} ผลลัพธ์
Count of number of non-increasing subarrays are: 7
คำอธิบาย
The subarrays will be −
{5}, {4}, {5}, {5,4} อินพุต
arr[] = {10,9,8,7} ผลลัพธ์
Count of number of non−increasing subarrays are − 10
คำอธิบาย
The subarrays will be −
{10}, {9}, {8}, {7}, {10,9}, {9,8}, {8,7}, {10,9,8}, {9,8,7}, {10,9,8,7} แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −
ในแนวทางนี้ เราจะใช้ข้อเท็จจริงที่ว่าหากองค์ประกอบระหว่างดัชนี i และ j ใน arr[] ไม่เพิ่มขึ้น องค์ประกอบระหว่างดัชนี i ถึง j+1, i ถึง j+2….i ถึง j+n-1 ไม่สามารถไม่เพิ่มขึ้นได้ ดังนั้นให้เพิ่มความยาวของ subarray นี้จนกว่าองค์ประกอบจะไม่เพิ่มขึ้น หากพบองค์ประกอบที่น้อยกว่า arr[j]
ใช้อาร์เรย์จำนวนเต็ม arr[].
ฟังก์ชั่น subarrays(int arr[], int size) ใช้อาร์เรย์และขนาดของอาร์เรย์และส่งกลับจำนวนอาร์เรย์ย่อยที่ไม่เพิ่มขึ้น
นับเริ่มต้นเป็น 0 และความยาวของ subarray ที่เล็กที่สุดเป็น temp=1
Traverse arr[] ใช้ for loop ถ้า arr[i + 1] <=arr[i] จะเพิ่มอุณหภูมิเนื่องจาก subarray จะไม่เพิ่มขึ้น
มิฉะนั้นให้เพิ่ม (temp + 1) * temp) / 2 เพื่อนับจำนวน subrrays ของ subarrayof length temp ซึ่งไม่เพิ่มขึ้น
ตั้งค่า temp=1 สำหรับอาร์เรย์ย่อยใหม่
ที่ส่วนท้ายของลูปทั้งหมด ถ้า length temp>
1 ให้เพิ่ม (temp + 1) * temp) / 2 เพื่อนับสำหรับอาร์เรย์ย่อยสุดท้าย
ผลตอบแทนนับเป็นผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int subarrays(int arr[], int size){
int count = 0;
int temp = 1;
for(int i = 0; i < size − 1; ++i){
if (arr[i + 1] <= arr[i]){
temp++;
} else {
count += (((temp + 1) * temp) / 2);
temp = 1;
}
}
if(temp > 1){
count += (((temp + 1) * temp) / 2);
}
return count;
}
int main(){
int arr[] = {2, 6, 1, 8, 3};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of number of non−increasing subarrays are: "<<subarrays(arr, size);
return 0;
} ผลลัพธ์
Count the number of non-increasing subarrays are: 7
