เราได้รับอาร์เรย์ Arr[] ของจำนวนเต็ม เป้าหมายคือการค้นหาอาร์เรย์ย่อยที่ยาวที่สุดของ Arr[] ผลรวมขององค์ประกอบที่เท่ากัน นั่นคือ ผลรวมขององค์ประกอบของอาร์เรย์ย่อยจะเท่ากัน และอาร์เรย์ย่อยนั้นมีความยาวสูงสุด
ป้อนข้อมูล − Arr[] ={ 2,3,5,2,6,7 }.
ผลผลิต −ความยาวสูงสุดของอาร์เรย์ย่อย − 4
คำอธิบาย −อาร์เรย์ย่อยความยาวสูงสุดคือ { 5,2,6,7 } ผลรวมคือ 20 ซึ่งเป็นคู่
ป้อนข้อมูล − Arr[] ={ 5,7,7,3,4 }.
ผลผลิต − ความยาวสูงสุดของ subarray − 4
คำอธิบาย − อาร์เรย์ย่อยความยาวสูงสุดคือ { 5,7,7,3 } ผลรวมคือ 22 ซึ่งเป็นคู่
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
อาร์เรย์จำนวนเต็ม Arr[] ใช้เพื่อเก็บจำนวนเต็ม
-
ขนาดตัวแปรใช้สำหรับเก็บความยาวของอาร์เรย์
-
Function Length( int arr[] ) คือการตรวจสอบผลรวมของอาร์เรย์เป็นคู่ เล้งใช้สำหรับเก็บความยาวของ subarray
-
คำนวณผลรวมทั้งหมดของอาร์เรย์ ถ้าส่งคืนความยาวของอาร์เรย์ n.
-
ตอนนี้เริ่มจากองค์ประกอบแรก สำรวจทั้งอาร์เรย์ หากพบองค์ประกอบคี่ ให้หาความยาวของทั้งสองครึ่งโดยไม่รวม arr[i]
-
คืนค่าความยาวสูงสุดของอาร์เรย์ย่อย
ตัวอย่าง
#include<iostream<
int Length(int arr[], int n){
int sum = 0, leng = 0;
// if whole array is even
for (int i = 0; i < n; i++)
sum += arr[i];
if (sum % 2 == 0) // total sum is already even
return n;
// Find an index i such the a[i] is odd
// and compare length of both halfs excluding
// a[i] to find max length subarray
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 1)
leng = i>n-i-1?i:n-i-1;
}
return leng;
}
int main(){
int Arr[] = { 1, 2, 6, 2, 4,2 };
int size = 6;
printf("Maximum length of subarray such that sum of the subarray is even: %d",Length(Arr, size));
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Maximum length of subarray such that sum of the subarray is even : 5
