计算之魂（吴军）1.3笔记，Datawhale组队学习Task02

心得分享：
1、同样的问题用分治、动态规划划分为小问题，让结果尽量靠近线性复杂度会从5级工程师变成2.5级工程师；
2、思考题1.3 Q1

var maxSubArrayDp = function(nums) {
    let pre = 0, maxAns = nums[0]
    nums.forEach((x) => {
        pre = Math.max(pre+x, x)
        maxAns = Math.max(maxAns, pre)
    });
    return maxAns
}

q1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
console.log(maxSubArrayDp(q1))
1
2
3
4
5
6
7
8
9
10
11

3、思考题1.3 Q2

var eqlSubArrayDp = function(nums, tar) {
    for (let i = 0; i < nums.length; i++) {
        let cnt = 0
        for (let j = i; j < nums.length; j++) {
            cnt += nums[j]
            if (cnt == tar) {
                return [i, j]
            }
        }
    }
}

q1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
console.log(eqlSubArrayDp(q1, -3))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4、思考题1.3 Q3