Krains's Blog

vuePress-theme-reco Krains    2020 - 2021
Krains's Blog Krains's Blog

Choose mode

  • dark
  • auto
  • light
Home
Category
  • Algorithm
  • LeetCode题解
  • 数据结构
  • 计算机基础知识
  • Java基础
  • Java多线程
  • JVM
  • MySQL
  • 设计模式
Tag
TimeLine
Contact
  • GitHub (opens new window)
author-avatar

Krains

80

Article

22

Tag

Home
Category
  • Algorithm
  • LeetCode题解
  • 数据结构
  • 计算机基础知识
  • Java基础
  • Java多线程
  • JVM
  • MySQL
  • 设计模式
Tag
TimeLine
Contact
  • GitHub (opens new window)

53. 最大子序和

vuePress-theme-reco Krains    2020 - 2021

53. 最大子序和


Krains 2020-08-20 10:46:24 动态规划前缀和

# 题目链接 (opens new window)

# 前缀和

看到子数组的题目,就应该想到前缀和,为了最大化子数组的和,假设我们有前缀和s,为了让子数组和最大,我们应该找出[i, j],使得s[j+1]-s[i]的差值最大:

ans=Max(s[j+1]−s[i]),j>=ians = Max(s[j+1]-s[i]),j>=i ans=Max(s[j+1]−s[i]),j>=i

为了最大化s[j+1]-s[i],遍历数组时记录最小的s[i],然后枚举s[j+1],求出最大的差值。

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        // 前缀和中首元素为0,因此这里min初始化为0
        int min = 0;
        int ans = nums[0];
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            ans = Math.max(sum-min, ans);
            min = Math.min(sum, min);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 动态规划

dp表示以元素nums[i-1]结尾的子数组的和

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int dp = nums[0];	// 用dp存状态
        int ans = nums[0];
        for(int i = 1; i < n; i++){
            // nums[i]加入dp代表的子数组的和与
            // 单独nums[i]为子数组的和相比较,取较大者
            dp = Math.max(nums[i], dp + nums[i]);
            ans = Math.max(ans, dp); 
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  • 题目链接
  • 前缀和
  • 动态规划