home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Maximum circular subarray sum in C++: หาผลรวม Subarray วงกลมสูงสุด

กำหนด array หา subarray (อาจพุ่งข้ามปลาย array) ที่มีผลรวมสูงสุด

ตัวอย่าง: {2, 5, -1, 6, 9, 4, -5} → Output: 25 (subarray: 4, 2, 5, -1, 6, 9)

วิธีแก้ปัญหา (Kadane's Algorithm แบบ Circular)

  1. หา max subarray sum ปกติ (max_kadane)
  2. หา min subarray sum (min_kadane)
  3. ผลรวมทั้งหมด = total
  4. Circular max = total - min_kadane (ยกเว้นกรณีทั้ง array เป็นลบ)
  5. คำตอบ = max(max_kadane, total - min_kadane)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int maximum(int arr[], int n) {
    int total = 0;
    for(int i=0;i

Input

{2, 5, -1, 6, 9, 4, -5}

Output

25