【CT】LeetCode手撕—53. 最大子数组和

---

题目

• 原题连接：53. 最大子数组和

---

1-思路

动规五部曲

• 1. 定义 dp 数组
  • dp[i] 含义为：下标为 i 的数组的最大子数组和
• 2. 递推公式
  • 因为所求的是最大子数组的和，即当前 nums 可加可不加，则需要在 dp[i-1]+nums[i] 和 nums[i] 两者中取一个较大的
  • dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
• 3. 初始化
  • dp[0] = nums[0]
• 4. 遍历顺序
  • 从 i = 0 遍历到 n-1

---

2- 实现

⭐53. 最大子数组和——题解思路

class Solution {public int maxSubArray(int[] nums) {// 1. 定义 dp数组// int[] dp = new int[nums.length];// 2.递推公式// dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);// 3.初始化dp[0] = nums[0];// 4. 遍历顺序for(int i = 1 ; i < nums.length;i++){dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);}int res = nums[0];for(int i:dp){res = Math.max(res,i);}return res;}
}

---

3- ACM 实现

public class maxSubNums {// 求 最大子数组和public static int maxSub(int[] nums){// 1.dp数组int[] dp = new int[nums.length];// 2.递推公式// dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);// 3.初始化dp[0] = nums[0];// 4.遍历顺序int res = nums[0];for(int i = 1 ; i < nums.length;i++){dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);res = Math.max(res,dp[i]);}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入数组的长度");int n = sc.nextInt();int[] nums = new int[n];for(int i = 0 ; i < n;i++){nums[i] = sc.nextInt();}System.out.println("最大子数组和为"+maxSub(nums));}
}