440. K-th Smallest in Lexicographical Order

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

Question

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

A subarray is a contiguous part of an array.

思路

这题其实和300题很相似，但是更简单。

定义好dp数组的意义，并且确定状态转移的方式，就会很简单。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    const dp = [];
    dp[0] = nums[0];
    let ret = nums[0];
    for (let i = 1; i < nums.length; i++) {
        const next = dp[i - 1] + nums[i];
        dp[i] = next >= nums[i] ? next : nums[i];
        ret = Math.max(dp[i], ret);
    }
    return ret;
};

总结

动态规划的题目其实有很多思路都是相同的。