Subarray ສູງສຸດໂດຍໃຊ້ Divide ແລະ Conquer


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ByteDance Cisco ເຟສບຸກ Goldman Sachs ກູໂກ JPMorgan LinkedIn Microsoft Oracle PayPal Paytm Uber
Array ແບ່ງແລະເອົາຊະນະ

ຖະແຫຼງການບັນຫາ

ໃນ "Sumarray Sum ສູງສຸດໂດຍໃຊ້ການແບ່ງປັນແລະເອົາຊະນະ" ບັນຫາທີ່ພວກເຮົາໄດ້ໃຫ້ໄວ້ array ຂອງທັງເລກບວກແລະລົບ. ຂຽນໂປຼແກຼມທີ່ຈະຊອກຫາຍອດຍ້ຽມທີ່ໃຫຍ່ທີ່ສຸດຂອງເສັ້ນທາງໃຕ້ດິນທີ່ຕິດຂັດ.

ຮູບແບບການປ້ອນຂໍ້ມູນ

ສາຍ ທຳ ອິດມີເລກ N.

ແຖວທີສອງປະກອບດ້ວຍອາເລຂອງເລກເຕັມເຊິ່ງບັນຈຸເລກເຕັມ N.

ຮູບແບບຜົນໄດ້ຮັບ

ພິມຄ່າເລກເຕັມເຊິ່ງ ໝາຍ ເຖິງ subarray ລວມຍອດສູງສຸດຂອງຂບວນການທີ່ໃຫ້.

ຂໍ້ ຈຳ ກັດ

  • 1 <= N <= 10 ^ 5
  • 1 <= a [i] <= 10 ^ 5

ຍົກຕົວຢ່າງ

5
-10 2 5 12 -5
19

ລະບົບວິເຄາະ

ນີ້ພວກເຮົາໃຊ້ ແບ່ງແລະເອົາຊະນະ ເຂົ້າຫາ. ພວກເຮົາສາມາດຊອກຫາຍອດ subarray ສູງສຸດໃນເວລາ O (nLogn). ຕໍ່ໄປນີ້ແມ່ນການແບ່ງປັນແລະແບ່ງປັນລະບົບ.

1. ແບ່ງອາເລເປັນສອງສ່ວນ.

2. ສືບຕໍ່ຊອກຫາຍອດ subarray ສູງສຸດ ສຳ ລັບ subarray ຊ້າຍ.

3. ຊອກຫາຕົວເລກ subarray ທີ່ສູງສຸດ ສຳ ລັບ subarray ທີ່ຖືກຕ້ອງ.

4. ຊອກຫາຍອດ subarray ສູງສຸດທີ່ຂ້າມຜ່ານຈຸດສູນກາງ.

5. ສົ່ງຄືນ ຈຳ ນວນເງິນສູງສຸດສາມຢ່າງຂ້າງເທິງ.

ສາຍ 2 ແລະ 3 ແມ່ນການໂທຫາແບບງ່າຍໆ. ວິທີການຊອກຫາຍອດ subarray ສູງສຸດເຊັ່ນວ່າ subarray ຂ້າມຈຸດສູນກາງ? ພວກເຮົາສາມາດຊອກຫາຍອດຂ້າມໃນເວລາເສັ້ນເປັນເສັ້ນໄດ້ຢ່າງງ່າຍດາຍ. ຄວາມຄິດດັ່ງກ່າວແມ່ນງ່າຍດາຍ, ຊອກຫາຍອດລວມສູງສຸດເລີ່ມຈາກຈຸດສູນກາງແລະສິ້ນສຸດໃນບາງຈຸດຢູ່ເບື້ອງຊ້າຍຂອງກາງ, ຫຼັງຈາກນັ້ນຊອກຫາຜົນລວມສູງສຸດເລີ່ມແຕ່ກາງ +1 ແລະສິ້ນສຸດດ້ວຍຈຸດລວມຢູ່ເບື້ອງຂວາ + ກາງ + 1 ສອງແລະກັບຄືນ.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບ Sumar Subarray ສູງສຸດໂດຍໃຊ້ Divide ແລະ Conquer

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

int cross_sum(int arr[], int l, int m, int h)
{
  int sum = 0;
  int left_sum = INT_MIN;
  for (int i = m; i >= l; i--) 
  {
    sum = sum + arr[i];
    if (sum > left_sum)
      left_sum = sum;
  }
  sum = 0;
  int right_sum = INT_MIN;
  for (int i = m + 1; i <= h; i++) 
  {
    sum = sum + arr[i];
    if (sum > right_sum)
      right_sum = sum;
  }
  return max(left_sum + right_sum, max(left_sum, right_sum));
}


int max_sum(int arr[], int l, int h)
{
  if(l==h)
  {
    return arr[l];
  }
  int m=(l+h)/2;
  return max(max_sum(arr, l, m), max(max_sum(arr, m + 1, h), cross_sum(arr, l, m, h)));
} 

int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int sum = max_sum(a,0,n-1);
  cout<<sum<<endl;
  return 0;
}

Java Program ສຳ ລັບ Sumar Subarray ສູງສຸດໂດຍໃຊ້ Divide ແລະ Conquer

import java.util.Scanner;
class sum
{
    public static int cross_sum(int arr[], int l, int m, int h)
    {
            int sum = 0;
            int left_sum = -1000000;
            for (int i = m; i >= l; i--) 
            {
                    sum = sum + arr[i];
                    if (sum > left_sum)
                            left_sum = sum;
            }
            sum = 0;
            int right_sum = -1000000;
            for (int i = m + 1; i <= h; i++) 
            {
                    sum = sum + arr[i];
                    if (sum > right_sum)
                            right_sum = sum;
            }
            return Math.max(left_sum + right_sum, Math.max(left_sum, right_sum));
    }
    public static int max_sum(int arr[], int l, int h) 
    {
        if(l==h)
  {
    return arr[l];
  }
  int m=(l+h)/2;
  return Math.max(max_sum(arr, l, m), Math.max(max_sum(arr, m + 1, h), cross_sum(arr, l, m, h)));
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int [n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum = max_sum(a,0,n-1);
        System.out.println(sum);
    }
}
7
10 5 -106 29 100 1000 -500
1129

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ Sumar Subarray ສູງສຸດໂດຍໃຊ້ການແບ່ງປັນແລະເອົາຊະນະ

ຄວາມສັບສົນເວລາ

ໂອ (n * logn) ບ່ອນທີ່ n ແມ່ນຂະ ໜາດ ຂອງອາເລທີ່ໃຫ້. ໃນທີ່ນີ້ພວກເຮົາມາພົວພັນກັບການພົວພັນກັບການເກີດຂື້ນນີ້ t (n) = 2 * t (n / 2) + θ (n). ເມື່ອພວກເຮົາແກ້ໄຂຄວາມ ສຳ ພັນກັບການເກີດຂື້ນນີ້ແລ້ວໄດ້ຮັບຄ່າຂອງ t (n) ເປັນ n * logn.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ເນື່ອງຈາກວ່າພວກເຮົາບໍ່ໄດ້ໃຊ້ບ່ອນຊ່ວຍຫຍັງຢູ່ທີ່ນີ້.