Max Subarray Sum

53. Maximum Subarray

gegeben: $a_1,a_2,\dots ,a_n\in \mathbb{Z}$ gesucht: $S_{i,j}=a_i+\cdots +a_j,i,j\in \{1\dots n\},i<j$ $S=0$ falls alle $a_k<0$

anders formuliert

The Naive Approach

for $i=1\dots n$ for $j=i\dots n$ $S_{i,j}={\sum }_{k=1}^j{a}_k$

Anzahl Addition: $A(n)\le {\sum }_{i=1}^n\frac{(n-i+1{)}^2}{2}=\frac{1}{2}(n^2+(n-1{)}^2+\cdots +1^2)=\frac{n(n+1)\left(n+\frac{1}{2}\right)}{6}\le O(n^3)$

Reduce Duplicate Work

Using Prefix sum $A(n)={\sum }_{i=1}^n(n-i)=\frac{n(n-1)}{2}=O(n^2)$

Divide and Conquer

divide and conquer.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’

Excalidraw Data

Text Elements

n/2

n/2

Fall 1

Fall 2

Fall 3

Lösung ganz links

Lösung ganz rechts

Lösung geht über die Mitte

（A(n) ≤ n/2-1)

Link to original

$S=max(Fal{l}_1,Fal{l}_2,Fal{l}_3)$

$n=1$ : $S=a_1$ falls $a_1>0$ sonst $S=0$

$A(n)=a\cdot n+2A\left(\frac{n}{2}\right)=2\left(2A\left(\frac{n}{2}\right)+a\frac{n}{2}\right)+an=2^{2}T\left(\frac{n}{4}\right)+2n=2^{\log n}A\left(\frac{n}{n}\right)+a\cdot n\cdot \log n$ $=c\cdot n+a\cdot n\log n$ $=O(n\log n)$

Another approach

Master Theorem

NOTE

$$T(n)=a\cdot T\left(\frac{n}{b}\right)+n^c$$

• $c>{\log }_{b}a⟹T(n)=O(n^c)$
• $c={\log }_{b}a⟹T(n)=O(n^c\log n)$
• $c<{\log }_{b}a⟹T(n)=O(n^{{\log }_{b}a})$

Example

$T(n)=2T\left(\frac{n}{2}+O(n)\right)$

• $a=2$
• $b=2$
• $c=1$ $⟹T(n)=O(n\log n)$

$T(n)=4T\left(\frac{n}{2}+O(n)\right)$

• $a=4$
• $b=2$
• $c=1$ $⟹T(n)=O(n^2)$

Link to original

Dynamic Programming

class Solution {
public:
  int maxSubArray(vector<int> &nums) {
    int n = nums.size();
    int currentsum = 0;
    int maxs = INT_MIN;
    int maxsum = INT_MIN;
    for (int i = 0; i < n; i++) {
      currentsum += nums[i];
      maxs = max(maxs, currentsum);
      if (currentsum < 0) {
        maxsum = max(maxsum, maxs);
        currentsum = 0;
        maxs = INT_MIN;
      }
    }
    maxsum = max(maxsum, maxs);
    return maxsum;
  }
};