date: 2024-02-28
title: "Divide-and-Conquer"
status: DONE
author:
  - AllenYGY
tags:
  - NOTE
  - DC
  - Algorithm
created: 2024-02-28
updated: 2024-04-17T17:24
publish: True

Divide-and-Conquer

Algorithm Algorithm Divide and Conquer

if $\text{sizeof}(P)$ is small then

return $\text{sol}(P)$

else

Split $P$ into $P_1, P_2, P_3, \ldots$

for $i \gets 1$ to $n$ do

$s_i \gets \text{DC}(P_i)$

end for

return $\text{combine}(s_1, s_2, \ldots)$

end if

Example By 2

Example By 2 and Solve it With n

Maximum Contiguous Subarray Problem

Input: R = [1 ... n] is an array of n integers
Output: R = R [i...j] is a subarray of R, s.t.
- A pair of two integer
- sum (R)=Sum(R[i...j]) is maximized
Respect to
- sum(R[i...j])=
Maximum
Subarray of R

Algorithm ReuseDataMCS ( R )

Input: An array R of n integers
Output: The value of MCS

VMAX = R[1],mi=0,mj=0
for i = 1 to N do 
	V = 0 
	for j = i to N do 
		// calculate V ( i, j )
		V = V + R [ j ] 
		if V > VMAX then 
			VMAX = V
			mi=i
			mj=j 
		end if
	end for
end for 
return VMAX

Algorithm Maximum Contiguous Subarray Problem {Brute Force Reuse Data}

$VMAX = R[1]$

$m_i = 0$

$m_j = 0$

for $i = 1$ to $N$ do

$V = 0$

for $j = i$ to $N$ do

//calculate $V(i, j)$

$V = V + R[j]$

if $V > VMAX$ then

$VMAX = V$

$m_i = i$

$m_j = j$

end if

end for

return $VMAX$

MCS(R, i, j)

Input: R[i...j]
Output: MCS of R[i...j]

Algorithm Maximum Contiguous Subarray Problem

if $i = j$ then

return $R[i]$

else

$s1 \gets \text{MCS}(R, i, \lfloor(i+j)/2\rfloor)$ //Using floor function for lower rounding

$s2 \gets \text{MCS}(R, \lfloor(i+j)/2\rfloor + 1, j)$

$A \gets \text{MaxSuffix}(R, i, \lfloor(i+j)/2\rfloor) + \text{MaxPrefix}(R, \lfloor(i+j)/2\rfloor + 1, j)$

return $\text{MAX}(s1, s2, A)$

end if

Cpp 解法

class Solution {
public:
	int maxPreffix(vector<int>&nums,int i ,int j){
		int ans=nums[i];
		int tmp=0;
		for(;i<=j;i++){
			tmp+=nums[i];
			if(tmp>ans){
				ans=tmp;
			}
		}
		return ans;
	}
	int maxSuffix(vector<int>&nums,int i ,int j){
		int ans=nums[j];
		int tmp=0;
		for(;i<=j;j--){
			tmp+=nums[j];
			if(tmp>ans){
			ans=tmp;
			}
		}
		return ans;
	}
	int MSA(vector<int>&nums,int i ,int j){
		if(i==j){
			return nums[i];
		}
		else{
			int S1=MSA(nums,i,(i+j)/2);
			int S2=MSA(nums,(i+j)/2+1,j);
			int A = maxSuffix(nums,i,(i+j)/2)+maxPreffix(nums,(i+j)/2+1,j);
			return max({S1,S2,A});
		}
	}
	int maxSubArray(vector<int>& nums) {
		return MSA(nums,0,nums.size()-1);
	}
};

Polynomial Multiplication

Definition: A x B
is the multiplication of A x B s.t
(i+j=k)0\leq k\leq n+m$$

Brute Force

Divide and Conquer

Algorithm Polynomial Multi1( $A(x),B(x)$ )

if $n=0$ then

return $a_0 \times b_0$

else

$A_0(x) = a_0 + a_1x + \dots + a_{\lfloor \frac{n}{2} \rfloor - 1}x^{\lfloor \frac{n}{2} \rfloor -1}$

$A_1(x) = a_{\lfloor \frac{n}{2} \rfloor} + a_{\lfloor \frac{n}{2} \rfloor +1}x + \dots + a_nx^{n-\lfloor \frac{n}{2} \rfloor}$

$B_0(x) = b_0 + b_1x + \dots + b_{\lfloor \frac{n}{2} \rfloor - 1}x^{\lfloor \frac{n}{2} \rfloor -1}$

$B_1(x) = b_{\lfloor \frac{n}{2} \rfloor} + b_{\lfloor \frac{n}{2} \rfloor +1}x + \dots + b_nx^{n-\lfloor \frac{n}{2} \rfloor}$

$U(x) = \text{PolyMult1}(A_0(x), B_0(x))$

$V(x) = \text{PolyMult1}(A_0(x), B_1(x))$

$W(x) = \text{PolyMult1}(A_1(x), B_0(x))$

$Z(x) = \text{PolyMult1}(A_1(x), B_1(x))$

return $U(x) + (V(x) + W(x))x^{\lfloor \frac{n}{2} \rfloor} + Z(x)x^{2\lfloor \frac{n}{2} \rfloor}$

end if

Time Complexity
Example By 2

Algorithm Polynomial Multi2( $A(x),B(x)$ )

if $n=0$ then

return $a_0 \times b_0$

else

$A_0(x) = a_0 + a_1x + \dots + a_{\lfloor \frac{n}{2} \rfloor - 1}x^{\lfloor \frac{n}{2} \rfloor -1}$

$A_1(x) = a_{\lfloor \frac{n}{2} \rfloor} + a_{\lfloor \frac{n}{2} \rfloor +1}x + \dots + a_nx^{n-\lfloor \frac{n}{2} \rfloor}$

$B_0(x) = b_0 + b_1x + \dots + b_{\lfloor \frac{n}{2} \rfloor - 1}x^{\lfloor \frac{n}{2} \rfloor -1}$

$B_1(x) = b_{\lfloor \frac{n}{2} \rfloor} + b_{\lfloor \frac{n}{2} \rfloor +1}x + \dots + b_nx^{n-\lfloor \frac{n}{2} \rfloor}$

$Y(x) = \text{PolyMult2}(A_0(x)+A_1(x), B_0(x)+B_1(x))$

$U(x) = \text{PolyMult2}(A_0(x), B_0(x))$

$Z(x) = \text{PolyMult2}(A_1(x), B_1(x))$

return $U(x) + (Y(x) - U(x) - Z(x))x^{\lfloor \frac{n}{2} \rfloor} + Z(x)x^{2\lfloor \frac{n}{2} \rfloor}$

end if