最大子数组和

53. 最大子数组和

leetcode 链接

思路：

动态规划

1.确定 dp 数组含义：dp[i] 表示以 i 为结尾的最大连续子数组和为 dp[i]

2.初始化 dp 数组，dp[0] = nums[0]

3.确定遍历方向，从前往后遍历

4.确定转移方程：当 dp[i - 1] 为负数时，则直接取 nums[i], 为正数时，则取 dp[i - 1]+nums[i]的值

5.将 dp 数组中的最大值返回即可

typescript 解法

function maxSubArray(nums: number[]): number {
  const length = nums.length;
  const dp: number[] = new Array(length).fill(0);
  let max: number = nums[0];
  dp[0] = nums[0];
  for (let i: number = 1; i < length; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    max = Math.max(dp[i], max);
  }
  return max;
}

go 解法

func maxSubArray(nums []int) int {
    length := len(nums)
    // 确定dp数组含义：dp 表示以i为结尾的最大连续子数组和为dp[i]
    dp := make([]int, length)
    // 初始化dp数组，默认第一个为nums[0]值
    dp[0] = nums[0]
    maxValue := nums[0]
    // 确定遍历方向
    for i := 1; i < length; i ++ {
        // 转移方程：当dp[i - 1]为负数时，则直接取nums[i], 为正数时，则取+nums[i]的值
        dp[i] = max(dp[i - 1] + nums[i], nums[i])
        if dp[i] > maxValue {
            maxValue = dp[i]
        }
    }
    return maxValue
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}