Recently in the interview, there is always a question, the first to see the question was confused, and then the second time to encounter, well, since I can not hide, then I sit down to reason, first understand the principle, and then to write code.

Requirement: please use js to find the largest subsequence in [3, -6, 123, -945, -231, 112].

What is the maximum subsequence? Look at a face of mengbi

[1, 1, 2], for example, the array and its subsequence is [1], [1, 1] [1, 1, 2], [1, 2], [2] (‘ in order to see clearly, here small make up with [] wrapped up ‘); I think you’ve already seen the idea of subsequences, which are different combinations, and the largest subsequence is the permutation that has the largest sum of subsequences.

Now that we understand the topic, let’s begin to analyze the principle.

  1. I want to find the left and right sorting combinations
  2. Find the sum of all sorts, find the one with the largest sum.

Three. Code

var ary=[3, -6, 123, -945, -231, 112]; // Step 1: Find all subsequence combinations; [[3], [3-6]...].  var allary=[]; // All subsequences -------------------------for(var i=0; i<ary.length; i++){let cur=ary[i];
    allary.push([ary[i]]);
    
    for(var j=i+1; j<ary.length; j++){letitem=ary.slice(i,j+1); allary.push(item); }} // Step 2: summation, find the maximum sumlet maxsum=null;
lettotalAry=[]; // Find the sum of all subsequencesletindex=null; // represents the index corresponding to maxsum in totalAryfor(var i=0; i<allary.length; i++){let total=allary[i].reduce((pre,cur)=>{
         returnpre+cur; }); totalAry.push(total); maxsum=maxsum>total? maxsum:total; Index = totalAry. FindIndex ((item)=>{return item==maxsum
    })
}
console.log(allary[index])

Copy the code

The general principle is this, here xiaobian will not encapsulate, do programmers you just so so, this code is easy to understand, but the lack of optimization, welcome to do a deeper version of the answer, let us improve together, let us the path of the program just so so!