# Dynamic Programming - Subarray

# Contiguous Subarray

#### Maximum Sum Subarray

Given an integer array `nums`

, find the contiguous subarray (containing at least one number) which has the largest **sum** and return its sum.

1 | // sum[i] : max sum of subarray end with nums[i] |

#### Maximum Product Subarray

Given an integer array `nums`

, find the contiguous subarray (containing at least one number) which has the largest **product** and return its product.

Considering that the product of two negative numbers can be bigger than two positive numbers, compared to the ‘maximum sum subarray’ problem, we save two intermediate results, thus `min`

and `max`

product of subarraies end with `nums[i]`

.

1 | // maxi[i] : max product of subarray end with nums[i] |

#### Number of Subarraies that Sum Equals K

**Array contains both positive and negative numbers.**

#### Number of Subarraies that Product Less Than K

**All posivite numbers.**

This is a two-pointer/sliding-window problem. The idea is always keep an `max-product-window`

less than K.

1 | shift window by adding a new number on the right; |

For window (5, 2), when 6 is introduced, it add 3 new subarray: {5}, {5, 2}, {5, 2, 6}.

1 | for (int left = 0, right = 0; j < nums.size(); right++) { |

#### Minimum Size Subarray Sum

Given an array of `n`

positive integers and a positive integer `s`

, find the minimal length of a **contiguous subarray** of which the `sum ≥ s`

. If there isn’t one, return 0 instead.

#### Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

# Discontinuous Subarray

#### Maximum Product of Three Numbers

Given an integer array, find three numbers whose product is maximum and output the maximum product.

1 | for (j = 3; j > 0; --j) { |