## Question

>[Leetcode 53. Maximum Subarray
](https://leetcode.com/problems/maximum-subarray/description/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
  let sum = 0;
  let max = Number.NEGATIVE_INFINITY;
  for(const num of nums){
    sum = sum + num;
 
    if(sum > max){
        max = sum;
    }
    if(sum < 0){
        sum = 0;
    }
  }  
  return max;
};

:::

<hr/>

### Sol

:::spoiler Code

var maxSubArray = function(nums) {
    let maxSubSum = nums[0];
    let cursum = 0;
    for(let i= 0; i<nums.length; i++){
        if(cursum < 0 ){
            cursum = 0
        }
        cursum = cursum + nums[i]
        maxSubSum = Math.max(maxSubSum, cursum)
    }
    return maxSubSum
};

:::

<hr/>

### 東
1. Divide and Conquer

2. Dynamic Programming

- Take one varibale as a global maximum to keep track maximum value
- `dp[i]` means max sum subarray ending at index `i`, if sum till `i-1` is is usefull, then take it otherwise take current cell value as sum till `i`

3. Greedy with Kadane's Algorithm

:::spoiler Code

// Time O(n) | Space O(1) - n is the length of input nums array
var maxSubArray = function(nums) {
    let maxSum = prevMaxSum = nums[0];
    for(let i = 1; i < nums.length; i++) {
        prevMaxSum = Math.max(prevMaxSum + nums[i], nums[i]);
        maxSum = Math.max(prevMaxSum, maxSum);
    }
    return maxSum;
};

//
var maxSubArray = function(nums) {
    return helper(nums, 0, nums.length - 1);
};

function helper(subNums, start, end) {
    if(start === end) return subNums[start];

    const mid = Math.floor((start + end)/2);
    
    let currLeftSum = 0;
    let leftMaxSum = -Infinity;
    for(let i = mid; i >= start; i--){
        currLeftSum += subNums[i];
        leftMaxSum = Math.max(currLeftSum, leftMaxSum);
    }

    let currRightSum = 0;
    let rightMaxSum = -Infinity;
    for(let i = mid + 1; i <=end ; i++){
        currRightSum += subNums[i];
        rightMaxSum = Math.max(currRightSum, rightMaxSum);
    }

    const maxLeftRight = Math.max(helper(subNums, start, mid), helper(subNums, mid + 1, end));
    return Math.max(maxLeftRight, rightMaxSum + leftMaxSum);
}

:::

<hr/>

### Jessie

[](https://hackmd.io/_uploads/BJAYIfJ8C.png)

:::spoiler Code

var maxSubArray = function (nums) {

    let currentSum = maxSum = nums[0];

    for (let i = 1; i < nums.length; i++) {
        let currentNum = nums[i];

        currentSum = Math.max(currentNum, currentSum + currentNum);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
};

:::

<hr/>

### Howard

:::spoiler Code

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # idea 1: DP
        # sub-problem: max local sub-array include index i 
        # so max local sub-array of i+1 is either (nums[i+1]_ or ((max local sub-array of i) + nums[i+1])
        # (Kadane's algorithm)
        # time O(n)
        # space O(1)
        current_max, max_til_now = 0, -inf
        
        for n in nums:
            current_max = max(n, current_max + n)
            max_til_now = max(current_max, max_til_now)
        return max_til_now

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::