Subarray ผลรวมที่ใหญ่ที่สุดต่อเนื่อง

กำหนดอาร์เรย์ของจำนวนเต็ม เราต้องหาผลรวมขององค์ประกอบทั้งหมดที่อยู่ติดกันซึ่งผลรวมมากที่สุดที่จะส่งเป็นผลลัพธ์

การใช้โปรแกรมไดนามิกเราจะเก็บผลรวมสูงสุดจนถึงเทอมปัจจุบัน จะช่วยในการค้นหาผลรวมขององค์ประกอบที่อยู่ติดกันในอาร์เรย์

อินพุตและเอาต์พุต

Input:
An array of integers. {-2, -3, 4, -1, -2, 1, 5, -3}
Output:
Maximum Sum of the Subarray is: 7

อัลกอริทึม

maxSum(array, n)

ป้อนข้อมูล - อาร์เรย์หลัก ขนาดของอาร์เรย์

ผลลัพธ์ − ยอดรวมสูงสุด

Begin
   tempMax := array[0]
   currentMax = tempMax
   for i := 1 to n-1, do
      currentMax = maximum of (array[i] and currentMax+array[i])
      tempMax = maximum of (currentMax and tempMax)
   done
   return tempMax
End

ตัวอย่าง

#include<iostream>
using namespace std;

int maxSum( int arr[], int n) {
   int tempMax = arr[0];
   int currentMax = tempMax;

   for (int i = 1; i < n; i++ ) { //find the max value
      currentMax = max(arr[i], currentMax+arr[i]);
      tempMax = max(tempMax, currentMax);
   }
   return tempMax;
}

int main() {
   int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
   int n = 8;
   cout << "Maximum Sum of the Sub-array is: "<< maxSum( arr, n );
}

ผลลัพธ์

Maximum Sum of the Sub-array is: 7