1.題目
給你一個整數陣列 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) 的解法，嘗試使用更為精妙的 分治法 求解，
2.題目分析
本道題也是一道動態規劃題目，
設dp[i]為該位置下的最大連續子陣列之和，
dp[i]=nums[i](當nums[i]>(dp[i-1]+nums[i]))
dp[i]=nums[i]+dp[i-1](當nums[i]<=(dp[i-1]+nums[i]))
??max=dp[i](max<dp[i])
3.代碼
class Solution {
public int maxSubArray(int[] nums) {
int length=nums.length;
int dp[]=new int[length];
int max=nums[0];
dp[0]=nums[0];
if(length ==1)
{
return max;
}
for(int i=1;i<length;i++)
{
int temp=nums[i]+dp[i-1];
if(nums[i]>(temp))
dp[i]=nums[i];
else
dp[i]=temp;
if(max<dp[i])
max=dp[i];
}
return max;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/517554.html
標籤：其他