> [!NOTE] Problem
> Given an array of $n$ integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.
# Divide & Conquer Solution
> [!NOTE] Solution
> Using [[Divide & Conquer Algorithm|divide & conquer]]:
> - Divide: we divide the array into subarrays $A\left[ 1,\dots, \frac{n}{2} \right]$ and $A\left[ \frac{n}{2}, \dots n \right]$
> - Conquer: We recursively solve each subproblem. Let $(i_{l},j_{l})$ denote the solution for left subarray and $(i_{r},j_{r})$ the solution for the right subarray.
> - Combine: Compute $i^{*}\in\left[ 1, \frac{n}{2} \right]$ which maximises $\sum_{i=i^{*}}^{\frac{n}{2}} A[k]$ and $j^{*}$ which maximises $\sum_{i=\frac{n}{2}+1}^{j^{*}} A[k]$. Return $\arg \max\left\{ S(i_{l},j_{l}), S(i_{r},j_{r}), S\left( i^{*}, \frac{n}{2} \right), S\left( \frac{n}{2} +1 , j^{*} \right), S(i^{*},j^{*} ) \right\}$ where $S(i,{j})= \sum_{k=i}^{j} = A[k]$.
>
### Worst Case Asymptotic Running Time
The running time satisfies $T(n) = T\left( \frac{n}{2} \right)+\Theta(n)$. Then $T(n) = \Theta(n\log n)$.
### Implementation
```run-python
def maxSubarray(A,l,r):
if l == r: return (l,r,A[l])
mid = (l+r)//2
i_l, j_l, S_ll = maxSubarray(A,l,mid)
i_r, j_r, S_rr = maxSubarray(A,mid+1,r)
i = mid
S_l = A[mid]; max_l = A[mid]
for k in range(mid-1,l-1,-1):
S_l = S_l + A[k]
if S_l > max_l:
max_l = S_l
i = k
j = mid+1
S_r = A[mid+1]; max_r = A[mid+1]
for k in range(mid+2,r+1):
S_r = S_r + A[k]
if S_r > max_r:
max_r = S_r
j = k
I = [max_l, max_r, max_r+max_l, S_ll, S_rr]
ans = I.index(max(I))
if ans == 0:
return (i,mid,max_l)
if ans == 1:
return (mid+1,j,max_r)
if ans == 2:
return (i,j,max_l+max_r)
if ans == 3:
return (i_l,j_l,S_ll)
if ans == 4:
return (i_r,j_r,S_rr)
A = [-1,3,-2,5,3,-5,2,2]
B = [2, -1, 2, 3, -4, 1, -2, 7, -5, 4]
print(maxSubarray(A,0,7))
print(maxSubarray(B,0,len(B)-1))
```
# Kadane's Algorithm
```run-python
def kadanes_algorithm_with_indices(arr):
max_current = max_global = arr[0]
start_index = end_index = temp_start_index = 0
for i in range(1, len(arr)):
if arr[i] > max_current + arr[i]:
max_current = arr[i]
temp_start_index = i
else:
max_current = max_current + arr[i]
if max_current > max_global:
max_global = max_current
start_index = temp_start_index
end_index = i
return start_index, end_index, max_global
A = [-1,3,-2,5,3,-5,2,2]
B = [2, -1, 2, 3, -4, 1, -2, 7, -5, 4]
print(kadanes_algorithm_with_indices(A))
print(kadanes_algorithm_with_indices(B))
```