# leetcode-53 DP is insteresting

https://leetcode.com/problems/maximum-subarray/

Each question in DP seems to be different, but the ideas are consistent.

Today we start with a simple question.

Question:

Given an integer array `nums`

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

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

If you want to exhaust all subarrays, the time complexity reaches to O(n2). This is obviously Time Limit Exceeded, but I did…= =!

1 | /** |

Stupid boy…

DP is insteresting, let’s think about this problem.

Assume it begins from one item `[1]`

, when add a item to the array, you should consider if the previous item is a positive number.

If it’s a positive number, then we can calculate the sum of these two number, two good brother.

Otherwise, if the previous item is a negative number, these two are not good brother, we will not calculate the sum.

Attention, `previous number`

can also be considered as `previous sum`

, understand? Now we have completed the decomposition of the goal problem to sum problem:

`maxSubArray(A, i) = A[i] + maxSubArray(A, i - 1) > 0 : maxSubArray(A, i - 1) : 0`

`i`

as the array size increases, `maxSubArray(A, i - 1)`

means the previous sum.

1 | var maxSubArray = function(A) { |

We can also reduse the complexity of space.

1 | /** |

再看这个问题爬楼梯问题，我们用dp思路考虑一下，

1 | var so = function(n) { |

选择问题，0或1，

如果有10个选择，最终有89条路，

如果有100个选择在你面前，有5x10^20条路，

全球有64x10^8个人，

妈呀算不过来了…😂

所以说世界上没有两片完全相同的叶子…

人生不到3w天

一天一个选择

那得有多少条路

哈哈哈哈哈😂 本来在写代码，写着写着写偏了

改天接着扯…