อาร์เรย์ย่อยผลรวมสูงสุดที่มีผลรวมน้อยกว่าหรือเท่ากับผลรวมที่กำหนดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์และผลรวม งานของเราคือการสร้างโปรแกรมที่จะหาผลรวม subarray สูงสุดที่มีผลรวมน้อยกว่าหรือเท่ากับผลรวมที่กำหนดใน c ++

เราต้องหาอาร์เรย์ย่อยที่มีความยาวน้อยกว่าหรือเท่ากับ n ซึ่งมีผลรวมน้อยกว่าหรือเท่ากับผลรวมที่กำหนด

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล − array ={3, 5, 1, 8, 2, 9}, ผลรวม =25

ผลผลิต − 25

คำอธิบาย − อาร์เรย์ย่อยที่มีผลรวมน้อยกว่าหรือเท่ากับ 25 คือ {5, 1, 8, 2, 9}

วิธีง่ายๆ วิธีหนึ่งในการหาอาร์เรย์ย่อยผลรวมสูงสุดคือการวนซ้ำบนอาร์เรย์และค้นหาผลรวมของอาร์เรย์ย่อยทั้งหมด จากนั้นจึงหาผลรวมที่ใกล้ที่สุดหรือเท่ากับ แต่วิธีนี้จะมีความซับซ้อนของเวลาของ O(n*n) เนื่องจากต้องใช้สองลูป

วิธีที่มีประสิทธิภาพมากขึ้นในการแก้ปัญหานี้คือการใช้ หน้าต่างบานเลื่อน กระบวนการ. ซึ่งเราจะตรวจสอบผลรวมปัจจุบันด้วยผลรวมสูงสุด และเพิ่มหรือลบองค์ประกอบในหน้าต่างตามการเปรียบเทียบ

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <iostream>
using namespace std;
int findMax(int a, int b){
   if(a>b)
      return a;
   return b;
}
int maxSumsubarray(int arr[], int n, int maxSum){
   int sum = arr[0], overallMax = 0, start = 0;
   for (int i = 1; i < n; i++) {
      if (sum <= maxSum)
      overallMax = findMax(overallMax, sum);
      while (sum + arr[i] > maxSum && start < i) {
         sum -= arr[start];
         start++;
      }
      sum += arr[i];
   }
   if (sum <= maxSum)
      overallMax = findMax(overallMax, sum);
   return overallMax;
}
int main(){
   int arr[] = {3, 1, 4, 7, 2, 9, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 20;
   cout<<"The maximum sum of subarray with sum less than or equal to "<<sum<<" is "<<maxSumsubarray(arr, n, sum);
   return 0;
}

ผลลัพธ์

The maximum sum of subarray with sum less than or equal to 20 is 18