題目描述：
方法一（暴力法）：
代碼（Java實作）：
class Solution {
int maxSubArray(int[] nums){
int i = 0;
int j = 0;
int MaxNums = nums[0];
int pre = 0;
for (i = 0; i < nums.length; i++)
{
pre = 0;
for (j = i; j < nums.length; j++)
{
pre += nums[j];
if (pre > MaxNums)
{
MaxNums = pre;
}
}
}
return MaxNums;
}
}
結果：
暴力法果然恐怖如斯…
方法二（動態規劃）：
代碼（Java實作）：
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0;
int MaxNums = nums[0];
for(int num : nums){
if(pre + num >= num){//如果現在子陣列的和加上一個數并且小于這個數，那么此時子陣列最大和為num，將num賦給pre，如果大于等于，則加上這個數，
pre = pre + num;
}else{
pre = num;
}
if(MaxNums >= pre){//MaxNums相當于已查找子陣列中的最大和，每找到一個新的子陣列后，都應比較此時的pre和MaxNums的大小，
continue;
}else{
MaxNums = pre;
}
}
return MaxNums;
}
}
結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/163126.html
標籤：其他
上一篇：6817. 【2020.10.07提高組模擬】DNA 序列
下一篇：維特比譯碼