使用javascript的最大子数组

本文介绍了使用javascript的最大子数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出一个整数数组nums

Given an integer array nums,

查找连续的子数组(包含至少一个数字)

find the contiguous subarray (containing at least one number)

具有最大的总和并返回其总和.

which has the largest sum and return its sum.

示例:

输入:[-2,1，-3,4，-1,2,1，-5,4]，

Input: [-2,1,-3,4,-1,2,1,-5,4],

输出:6

说明:[4，-1,2,1]的总和= 6.

Explanation: [4,-1,2,1] has the largest sum = 6.

输入:[-1]

输出:-1

输入:[-2，-1]

Inputs:[-2,-1]

输出:[-1]

我在JS中尝试的方法:

What i try in my JS:

var maxSubArray = function(nums) { result=0 negativenumber=[] for(i=0;i<nums.length;i++){ if(nums[i]<0){ negativenumber.push(nums[i]); }else{ result+=nums[i]; } } return result; }; maxSubArray([-2,1,-3,4,-1,2,1,-5,4])//should return 6 maxSubArray([-1])//should return -1 maxSubArray([-1,-2])//should return -1

推荐答案

您可以使用 Kadane的算法.

function maxSum(arr){ let a1 = 0 let a2 = arr[0] arr.forEach((i,a) => { a1 = Math.max(i, a1 + i) a2 = Math.max(a2, a1) }) return a2 } console.log(maxSum([-2,1,-3,4,-1,2,1,-5,4])) console.log(maxSum([-1])) console.log(maxSum([-1,-2]))