题目来自LeetCode
链接：https://leetcode-cn.com/problems/generate-parentheses

题目出自LeetCodehttps://leetcode-cn.com

乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

var maxProduct = function (nums) {
   //令max为当前最大值，则max=Math.max(max*nums[i],nums[i]) 由于存在负数所以要维护 min=Math.min(min*nums[i],nums[i]) 
    let max = -Infinity,imax=1,imin=1
    for(let i =0;i<nums.length;i++){
        //如果有负数时 imax与imin交换
        if(nums[i]<0){
            let tmp = imax
            imax = imin
            imin = tmp
        }
        imax = Math.max(imax*nums[i],nums[i])
        imin = Math.min(imin*nums[i],nums[i])
        max = Math.max(max,imax)
    }
    return max
};

最大子序列和

动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果

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

最长回文子串

var longestPalindrome = function (s) {
    let len = s.length
    let result
    let i,j,L
    let dp = Array(len).fill(0).map(x=>Array(len).fill(0))
    if(len<=1) return s
    for(i =0;i<len;i++){
        dp[i][i] = 1
        result = s[i]
    }
    for(L=2;L<=len;L++){
        for(i=0;i<=len-L;i++){
            j=i+L-1
            if(L===2 && s[i]===s[j]){
                dp[i][j] = 1
                result = s.slice(i,i+L)
            }else if(s[i]==s[j] && dp[i+1][j-1]==1){
                dp[i][j]=1
                result = s.slice(i,i+L)
            }
        }
    }
    return result
};

最长上升子序列

var lengthOfLIS = function (nums) {
    if (nums.length <= 1) return nums.length
    dp = new Array(nums.length).fill(1)
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp)
};