Leetcode練習53. 最大子序(附加變種)

題目 難度-簡單

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。

解題思路
1.先取第一個值，作為最大值max
2.設置一個累加結果值 sum=0;
3.判斷累加結果值是否大於0，大於0,則繼續累加當前值，否則將sum=nums[i];
4.比較這一輪的sum 與max 的大小。取大的值為max;
5.返回max;
具體代碼
const maxSubArray = function (nums) {
    let max = nums[0];
    let sum = 0;
    for (let i = 1; i < nums.length; i++) {
        sum = sum < 0 ? nums[i] : sum + nums[i];
        max = Math.max(sum, max);
    }
    return max;
};

var nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
var result = maxSubArray(nums);
console.log(result);
附加題 如果還需要知道 最大子序的起始點和終結點
解題思路
1.可以增加 四個變量進行存儲，start,end,finialStart,finialEnd;
2.如果累加值小於0，則，start=end=i; 如果累加值大於0,則end=i;
3.判斷累加值是否大於max,大於則更新 finialStart=start,finialEnd=end;
具體代碼
const maxSubArray = function (nums) {
    let max = nums[0];
    let sum = 0;
    let start = 0, end = 0, finialStart = 0, finialEnd = 0;
    for (let i = 1; i < nums.length; i++) {
        if (sum < 0) {
            sum = nums[i];
            end = start = i;
        } else {
            sum += nums[i];
            end = i;
        }
        if (sum > max) {
            max = sum;
            finialEnd = end;
            finialStart = start;
        }
    }
    console.log(max, finialStart, finialEnd);
    return max;
};

var nums = [-2, 1, -3, 4, -1];

var result = maxSubArray(nums);