อัลกอริทึมของ Kadence: อาร์เรย์ย่อยที่ต่อเนื่องกันที่ใหญ่ที่สุด

อาร์เรย์ย่อยที่อยู่ติดกันผลรวมที่ใหญ่ที่สุดคืออะไร?

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

ตัวอย่างเช่น อาร์เรย์คือ {-10, 5, 1, 6, -9, 2, -7, 3, -5} อาร์เรย์ย่อยอาจเป็น: {-10,5,1,6} หรือ {5,1,6} หรือ {2,7,3, -5} เป็นต้น แต่ {5,1,6,3} ไม่สามารถเป็น อาร์เรย์ย่อยเนื่องจากไม่ได้รักษาลำดับไว้

ถ้าคุณสังเกต ในบรรดาซับอาร์เรย์ทั้งหมด ซับอาร์เรย์ที่เน้นข้อความไว้ดังต่อไปนี้ (5,1,6) มีค่าผลรวมสูงสุด:

ผลรวมของอาร์เรย์ย่อย {5,1,6} = 11 คือผลรวมสูงสุดในการรวมกันที่เป็นไปได้ทั้งหมดของอาร์เรย์ย่อยของอาร์เรย์ด้านบน ดังนั้น สำหรับอาร์เรย์ด้านบน อาร์เรย์ย่อยสูงสุดคือ {5,1,6}

อัลกอริทึมของ Kadence: อาร์เรย์ย่อยที่ต่อเนื่องกันที่ใหญ่ที่สุด

วิธีการง่ายๆ ในการแก้อาร์เรย์ย่อยที่ต่อเนื่องกันมากที่สุด

วิธีง่ายๆ ในการแก้ปัญหานี้คือการใช้สองลูปเพื่อค้นหาอาร์เรย์ย่อยทั้งหมด คำนวณผลรวม จากนั้นหาค่าสูงสุด

ต่อไปนี้เป็นผังงานสำหรับแนวทางง่ายๆ ในการค้นหาอาร์เรย์ย่อยที่ต่อเนื่องกันมากที่สุด นี่เป็นแนวทางแบบเดรัจฉาน ขณะที่เรากำลังผ่านอาร์เรย์ย่อยที่เป็นไปได้ทั้งหมด

นี่คือขั้นตอนง่าย ๆ ในการทำเช่นนี้

ขั้นตอน 1) เริ่มต้น max_sum ด้วยค่าจำนวนเต็มขั้นต่ำ และกำหนดตัวแปร “begin” และ “end” ด้วยศูนย์

ขั้นตอน 2) ให้ i และ j เป็นดัชนีของอาร์เรย์ โดยที่ "j" มากกว่าเท่ากับ "i" แสดงถึงดัชนีเริ่มต้นของอาร์เรย์ย่อย และ "j" แสดงถึงดัชนีสิ้นสุดของอาร์เรย์ย่อย

ขั้นตอน 3) “Current_sum” จะเก็บผลรวมของอาร์เรย์ย่อย หลังจากคำนวณผลรวมปัจจุบันแล้ว ให้ตรวจสอบว่า current_sum มากกว่า max_sum หรือไม่

ขั้นตอน 4) หาก current_sum มากกว่า ให้แทนที่ max_sum ด้วยผลรวมปัจจุบัน

ขั้นตอน 5) ตรวจสอบว่า "j" ไปถึงจุดสิ้นสุดของอาร์เรย์หรือไม่ หาก “j” ถึงจุดสิ้นสุดของอาร์เรย์ ให้เพิ่ม “i” และเปลี่ยนค่า current_sum เป็น 0

ขั้นตอน 6) ทำตามขั้นตอนเหล่านี้ทั้งหมด จนกระทั่ง “i” ถึงจุดสิ้นสุดของอาร์เรย์

ขั้นตอน 7) ที่จุดสิ้นสุดของสองลูปนี้ max_sum จะเก็บผลรวมอาร์เรย์ย่อยที่ใหญ่ที่สุด

รหัสหลอกสำหรับแนวทางง่ายๆ

  function maximumSubarraySum():
    input: array
  for all possible subArray from array:
    calculate sum of each sub array
    store the maximum subArray
  return the maximum sum

C++ การดำเนินการตามแนวทางง่ายๆ

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
  int max_sum = -1e9;
  int begin = 0;
  int end = 0;
  for (int i = 0; i < n; i++) {
    int current_sum = 0;
    for (int j = i; j < n; j++) {
      current_sum += array[j];
      if (max_sum < current_sum) {
        max_sum = current_sum;
        begin = i;
        end = j;
      }
    }
  }
  cout << "largest sum is " << max_sum << endl;
  cout << "largest sum contiguous subarray: ";
  for (int i = begin; i <= end; i++) {
    cout << array[i] << "\t";
  }
}
int main() {
  int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
  maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

Output:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python การนำแนวทางง่ายๆ ไปใช้

def maximumSubarraySum(numbers):
max_sum,begin,end = -1e9, 0 , 0
  for i in range(len(numbers)):
    current_sum=0
  for j in range(i,len(numbers)):
    current_sum+=numbers[j]
  if max_sum<current_sum:
    max_sum=current_sum
  begin,end=i,j
    print("largest sum is ",max_sum)
    print("largest sum contiguous subarray: ",end="")
  for i in range(begin,end+1):
    print(numbers[i],end='\t')
    numbers = [-10,5,1,6,-9,2,-7,3,-5]
    maximumSubarraySum(numbers)

Output:

largest sum is 12
largest sum contiguous subarray: 5      1       6

อัลกอริทึมของ Kadane เพื่อค้นหาอาร์เรย์ย่อยที่ต่อเนื่องกันมากที่สุด

อัลกอริทึมของ Kadane เป็นวิธี "การเขียนโปรแกรมแบบไดนามิก" ประเภทหนึ่ง ที่นี่เราจะใช้หนึ่งวงแทนสองวง การใช้งานอัลกอริทึมของ Kadane โดยทั่วไปใช้ได้กับอาร์เรย์จำนวนบวกเท่านั้น

เราต้องการเพียงตัวแปรสองตัวเพื่อค้นหาอาร์เรย์ย่อยที่ต่อเนื่องกันมากที่สุด นี่คือผังงานสำหรับอัลกอริทึมของ Kadane:

ต่อไปนี้เป็นขั้นตอนสำหรับอัลกอริทึมของ Kadane:

ขั้นตอน 1) สร้างตัวแปรสองตัว ได้แก่ current_sum และ max_sum

“Current_sum” จะเก็บค่าของผลรวมสูงสุดที่ลงท้ายด้วยดัชนีอาร์เรย์เฉพาะ ในขณะที่ “max_sum” จะเก็บค่าผลรวมสูงสุดจนถึงตอนนี้

ขั้นตอน 2) เราจะเพิ่มค่าด้วย current_sum สำหรับแต่ละองค์ประกอบอาร์เรย์ จากนั้นเราจะตรวจสอบเงื่อนไขสองประการด้านล่าง:

• หาก current_sum น้อยกว่าองค์ประกอบปัจจุบัน ค่า current_sum จะเป็นองค์ประกอบปัจจุบัน
• หาก max_sum น้อยกว่า current_sum ดังนั้น max_sum จะเป็น current_sum

ขั้นตอน 3) ดำเนินการขั้นตอนก่อนหน้าสำหรับอาร์เรย์ทั้งหมด เราจะมีอาร์เรย์ย่อยที่ต่อเนื่องกันมากที่สุดในตัวแปร "max_sum"

ตัวอย่างอัลกอริทึมของ Kadane

เราจะสาธิตอัลกอริทึมของ Kadanes ด้วยอาร์เรย์ขนาดเล็ก และอภิปรายทุกขั้นตอนในการค้นหาอาร์เรย์ย่อยที่ต่อเนื่องกันที่ใหญ่ที่สุด

สมมติว่าอาร์เรย์ที่กำหนดเป็นดังต่อไปนี้:

ต่อไปนี้เป็นขั้นตอนของอัลกอริทึมของ Kadane:

ขั้นตอน 1) สร้างตัวแปรสองตัวคือ current_sum และ max_sum กำหนด INT_MIN ให้กับ max_sum และ 0 ให้กับ current_sum (ในที่นี้ INT_MIN หมายถึงจำนวนเต็มขั้นต่ำ)

ขั้นตอน 2) ที่ดัชนี 0 ค่าคือ 4 ดังนั้น current_sum = 0 + 4 หรือ 4 ที่นี่ current_sum มีขนาดใหญ่กว่า max_sum โดย max_sum จะเป็น 4

ขั้นตอน 3) ที่ดัชนี 1 ค่าคือ -2 ดังนั้น current_sum = 4 + (-2) หรือ 2

คราวนี้ current_sum น้อยกว่า max_sum ด้วยเหตุนี้ ค่าของ max_sum จะไม่ถูกอัปเดต

ขั้นตอน 4) ค่าถัดไปคือ 1 หากเราเพิ่มสิ่งนี้ด้วย current_sum แล้ว current_sum จะเป็น 3 แต่ max_sum นั้นมากกว่า current_sum ดังนั้น max_sum จะไม่ได้รับการอัปเดต

ขั้นตอน 5) ที่ดัชนี 3 ค่าคือสาม เราจะอัปเดตค่าโดยการเพิ่ม current_sum ขึ้น 3 ดังนั้น current_sum จะเป็น 6

ในกรณีนี้ max_sum จะน้อยกว่า current_sum ดังนั้น max_sum จะได้รับการอัปเดตด้วยค่า current_sum

ขั้นตอน 6) สำหรับองค์ประกอบสุดท้ายของอาร์เรย์ เราได้ -1 หากเราเพิ่มสิ่งนี้ด้วย current_sum แล้ว current_sum จะเป็น 5 ซึ่งน้อยกว่า max_sum ดังนั้น max_sum จะยังคงเป็น 6

เมื่อเรามาถึงจุดสิ้นสุดของอาร์เรย์ อัลกอริธึมจะสิ้นสุดที่นี่ ตอนนี้ “max_sum” มีอาร์เรย์ย่อยผลรวมสูงสุด ซึ่งก็คือ 5 อาร์เรย์ย่อยคือ {4,-2,1,3}

รหัสหลอกสำหรับอัลกอริทึมของ Kadane

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each elements in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++การใช้อัลกอริทึมของ Kadane

#include < iostream >
using namespace std;
void kadane(int array[], int n) {
  int current_sum = 0;
  int max_sum = -1e9;
  // -1e9 means -10000000
  for (int i = 0; i < n; i++) {
    current_sum += array[i];
    if (max_sum < current_sum) {
      max_sum = current_sum;
    }
    if (current_sum < array[i]) {
      current_sum = array[i];
    }
  }
  cout << "largest sum is " << max_sum << endl;
}
int main() {
  int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
  kadane(array, sizeof(array) / sizeof(array[0]));
}

Output:

largest sum is 12

Python การใช้อัลกอริทึมของ Kadane

def kadane(numbers):
  current_sum = 0
  max_sum = -1e9
for i in range(len(numbers)):
  current_sum += numbers[i]
if max_sum < current_sum:
  max_sum = current_sum
if current_sum<numbers[i]:
  current_sum = numbers[i]
  print("largest sum is ",max_sum)
  kadane([-10,5,1,6,-9,2,-7,3,-5])

Output:

largest sum is 12

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

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

หากอาร์เรย์มีผลรวมเป็น N องค์ประกอบต่างๆ จากนั้นใช้สองลูป เราจะผ่าน N² องค์ประกอบ ดังนั้น ความซับซ้อนของเวลาสำหรับวิธีการง่ายๆ ในการค้นหาผลรวมที่ใหญ่ที่สุดของซับอาร์เรย์ที่อยู่ติดกันจะเป็นดังนี้ O(N2). ที่นี่ “O” หมายถึงฟังก์ชันความซับซ้อน

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

ดังนั้นหากอาร์เรย์อินพุตมีขนาดเท่ากับ Nดังนั้นความซับซ้อนของเวลาของอัลกอริทึมของ Kadane จะเป็น O(N) ซึ่งเร็วกว่าวิธีการแบบง่าย ๆ เช่น อาร์เรย์ที่มีองค์ประกอบ 100 องค์ประกอบ วิธีการแบบง่าย ๆ จะใช้เวลา CPU 100*100 หรือ 10,000 แต่อัลกอริทึมของ Kadane จะใช้เวลา CPU เพียง 100 เท่านั้น