一、題目大意
標簽: 動態規劃
https://leetcode.cn/problems/maximum-subarray
給你一個整數陣列 nums ，請你找出一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，
子陣列 是陣列中的一個連續部分，
示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子陣列 [4,-1,2,1] 的和最大，為 6 ，
示例 2：
輸入：nums = [1]
輸出：1
示例 3：
輸入：nums = [5,4,-1,7,8]
輸出：23
提示：
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
進階：如果你已經實作復雜度為 O(n) 的解法，嘗試使用更為精妙的 分治法 求解，
二、解題思路
定義一個max保存遍歷程序中出現的最大子陣列和，也是回傳結果，定義一個dp[i]，用來表示以第i個元素為結尾的陣列的最大陣列和，狀態轉移方程為：dp[i] = max(dp[i-1]+nums[i], nums[i])
三、解題方法
3.1 Java實作
public class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
max = Math.max(dp[i], max);
}
return max;
}
}
四、總結小記
- 2022/7/6 程式員是不是也有“文人相輕”的毛病
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498627.html
標籤：其他
上一篇：「筆記」折半搜索（Meet in the Middle）
下一篇：演算法競賽進階指南0x41并查集