ในปัญหานี้ เราได้รับอาร์เรย์และจำนวนเต็ม k งานของเราคือสร้างโปรแกรมที่จะหาผลรวมสูงสุดของความยาวอาร์เรย์ย่อยที่ไม่ทับซ้อนกันโดยมี k เป็นองค์ประกอบสูงสุดใน c++
คำอธิบายปัญหา – ในที่นี้ เรามีอาร์เรย์และจำนวนเต็ม k เราต้องหาอาร์เรย์ย่อยที่ไม่ทับซ้อนกันที่เป็นไปได้ทั้งหมดที่สามารถสร้างได้จากอาร์เรย์นี้ และรวมความยาวของอาร์เรย์ย่อยทั้งหมดที่สร้างขึ้น
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล − อาร์เรย์ ={3, 7, 1, 2, 3, 1, 6, 3, 2, 5} k =3
ผลผลิต − 7
คำอธิบาย − อาร์เรย์ย่อยที่ไม่ทับซ้อนกันที่มีองค์ประกอบสูงสุด 3:
{3} : length = 1
{1, 2, 3, 1} : length = 4
{3, 2} : length = 2
Sum of length = 1+4+2 = 7 ในการแก้ปัญหานี้ เราจะสำรวจอาร์เรย์และค้นหาองค์ประกอบทั้งหมดที่น้อยกว่าและรักษาความยาวไว้ หากอาร์เรย์ย่อย (สตรีมขององค์ประกอบ) มี k ให้เพิ่มความยาวเพื่อรวม
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
int subArrayLengthSum(int arr[], int n, int k){
int lengthSum = 0;
int subarrayLength = 0;
int flag = 0;
for (int i = 0; i < n;) {
subarrayLength = 0;
flag = 0;
while (arr[i] <= k && i < n) {
subarrayLength++;
if (arr[i] == k)
flag = 1;
i++;
}
if (flag == 1)
lengthSum += subarrayLength;
while (arr[i] > k && i < n)
i++;
}
return lengthSum;
}
int main(){
int arr[] = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 3;
int ans = subArrayLengthSum(arr, size, k);
cout<<"The max sum of lengths of non-overlapping subarrays with "<<k<<" as max element is "<<ans;
return 0;
} ผลลัพธ์
The max sum of lengths of non-overlapping subarrays with 3 as max element is 7
