โจทย์ปัญหา

Problem 53 - Maximum Subarray

Problem: https://leetcode.com/problems/maximum-subarray/

ปัญหา Maximum Subarray เป็นหนึ่งในโจทย์ปัญหาคลาสสิกบน LeetCode ซึ่งมีรายละเอียดโจทย์ดังนี้
กำหนดอาร์เรย์ของจำนวนเต็ม nums ให้หา subarray ที่ต่อเนื่องกัน (มีอย่างน้อยหนึ่งจำนวน) ซึ่งให้ผลรวมมากที่สุด และคืนค่าผลรวมนั้นตัวอย่างเช่น:

• Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
• Output: 6
• คำอธิบาย: subarray [4,-1,2,1] ให้ผลรวมมากที่สุดเท่ากับ 6

ข้อนี้สามารถแก้ปัญหาได้จากการใช้ Divied & Conquer โดย

1. แบ่งอาร์เรย์ออกเป็น 2 ส่วนเท่าๆ กัน โดยใช้ตำแหน่งกึ่งกลาง (mid)
   • ส่วนซ้าย (left) คือช่วงตั้งแต่ตำแหน่งเริ่มต้น (start) ถึง mid
   • ส่วนขวา (right) คือช่วงตั้งแต่ตำแหน่ง mid+1 ถึงตำแหน่งสุดท้าย (end)
2. เรียกใช้ function แบบ recursive กับส่วนซ้ายและส่วนขวา โดยการ
   • หาผลรวม subarray มากสุดในส่วนซ้าย (leftSum)
   • หาผลรวม subarray มากสุดในส่วนขวา (rightSum)
   • หาผลรวม subarray มากสุดที่ข้ามผ่านจุดกึ่งกลาง (crossSum)
3. คืนค่ามากสุดใน leftSum, rightSum และ crossSum จะได้เป็นคำตอบของ subarray ที่มีผลรวมมากที่สุดในช่วงปัจจุบันออกมาได้

c++ solution

class Solution {
public:
  int crossSum(vector<int> &nums, int left, int mid, int right) {
    int leftSum = INT_MIN;
    int currSum = 0;

    for (int i = mid; i >= left; i--) {
      currSum += nums[i];
      leftSum = max(leftSum, currSum);
    }

    int rightSum = INT_MIN;
    currSum = 0;

    for (int i = mid + 1; i <= right; i++) {
      currSum += nums[i];
      rightSum = max(rightSum, currSum);
    }

    return leftSum + rightSum;
  }

  int maxSubArraySum(vector<int> &nums, int left, int right) {
    if (left == right) {
      return nums[left];
    }

    int mid = left + (right - left) / 2;

    int leftSum = maxSubArraySum(nums, left, mid);
    int rightSum = maxSubArraySum(nums, mid + 1, right);
    int crossSumResult = crossSum(nums, left, mid, right);

    return max(max(leftSum, rightSum), crossSumResult);
  }

  int maxSubArray(vector<int> &nums) {
    return maxSubArraySum(nums, 0, nums.size() - 1);
  }
};

วิเคราะห์ Time Complexity ของ Algorithm

• function crossSum มี Time Complexity เป็น O(n) เนื่องจากใช้ loop เดินทางซ้ายและขวาของจุดกึ่งกลาง
• function maxSubArraySum มี Time Complexity เป็น O(n log n) เนื่องจากแบ่งปัญหาเป็น 2 ส่วนย่อยในแต่ละระดับของ recursion และมีการเรียกใช้ function crossSum ที่มี complexity O(n) ในแต่ละระดับด้วย
• ดังนั้น Time Complexityคือ O(n log n)

สรุป

• algorithm Divide and Conquer ถูกใช้ในการแก้ปัญหา Maximum Subarray โดยแบ่งอาร์เรย์ออกเป็นส่วนย่อยซ้ำๆ จนกว่าจะเหลือเพียงหนึ่งองค์ประกอบ
• ในแต่ละระดับของ recursion จะหาผลรวม subarray มากสุดในครึ่งซ้าย ครึ่งขวา และผ่านจุดกึ่งกลาง แล้วเลือกค่าที่มากที่สุดเป็นคำตอบ
• Time Complexity ของ algorithm นี้คือ O(n log n) ซึ่งถือว่ามีประสิทธิภาพดี แม้จะไม่ใช่วธีที่เร็วที่สุดสำหรับปัญหานี้ก็ตาม

สรุปส่งท้าย

Divide and Conquer เป็นเทคนิคการออกแบบ algorithm ที่มีประสิทธิภาพและเอนกประสงค์ ซึ่งใช้หลักการ "แบ่งแยกและเอาชนะ" ในการแก้ปัญหาที่ซับซ้อน วิธีการหลักของ Divide and Conquer คือการแบ่งปัญหาใหญ่ออกเป็นปัญหาย่อยที่มีขนาดเล็กลง จากนั้นจึงแก้ปัญหาย่อยเหล่านั้นแบบ recursive จนกว่าจะเล็กพอที่จะแก้ได้ง่าย แล้วจึงรวมคำตอบของปัญหาย่อยเพื่อสร้างคำตอบของปัญหาใหญ่ขึ้นมา

algorithm ที่ใช้ Divide and Conquer มีหลากหลาย เช่น Merge Sort, Quick Sort, Karatsuba Multiplication เป็นต้น ซึ่งแต่ละ algorithm จะมีวิธีการแบ่งปัญหาและรวมคำตอบที่แตกต่างกันไป แต่ก็ยึดหลักการพื้นฐานของ Divide and Conquer เหมือนกัน นอกจากนี้ Divide and Conquer ยังสามารถประยุกต์ใช้กับปัญหาในหลายสาขา เช่น การประมวลผลกราฟิก, การค้นหาและเรียงลำดับข้อมูล, การคำนวณทางคณิตศาสตร์ เป็นต้น

ข้อดีของ Divide and Conquer คือช่วยลด complexity ของปัญหาให้เหลือเพียงปัญหาย่อยที่ง่ายกว่า และสามารถทำงานแบบขนานได้เนื่องจากปัญหาย่อยมีความเป็นอิสระต่อกัน ทำให้ประหยัดเวลาในการประมวลผลได้มาก อย่างไรก็ตาม Divide and Conquer ก็มีข้อจำกัดบางประการ เช่น อาจต้องใช้หน่วยความจำเพิ่มขึ้นเพื่อเก็บข้อมูลระหว่างการทำ recursion, การแบ่งปัญหาและรวมคำตอบอาจมี complexity สูง, และอาจไม่เหมาะกับปัญหาบางประเภทที่ไม่สามารถแบ่งเป็นปัญหาย่อยได้

โดยสรุป Divide and Conquer เป็นกลยุทธ์ที่ทรงพลังในการออกแบบ algorithm ที่มีประสิทธิภาพสูง โดยอาศัยหลักการแบ่งปัญหาใหญ่ให้เป็นปัญหาเล็ก แก้ปัญหาเล็กแบบ recursive และรวมคำตอบเข้าด้วยกันอย่างเป็นระบบ ซึ่งช่วยให้สามารถจัดการกับปัญหาที่ซับซ้อนและมีขนาดใหญ่ได้อย่างมีประสิทธิภาพ แม้จะมีข้อจำกัดบางประการ แต่ Divide and Conquer ก็ยังคงเป็นเครื่องมือสำคัญที่นักพัฒนา algorithm ต้องเข้าใจและนำไปประยุกต์ใช้ให้เหมาะสมกับปัญหาต่างๆ เพื่อให้ได้วิธีการแก้ปัญหาที่ดีที่สุดออกมานั่นเอง