Skip to main content

From an array of integers, find the contiguous subarray which has the largest sum

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example Problem:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Here is the shortest solution with a time complexity of O(n) in javascript to the maximum subarray problem:
var maxSubArray = function(nums) {
    for (let i = 1; i < nums.length; i++){
        nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
    }
    return Math.max(...nums);
};
Try out this in live editor: https://repl.it/@VinitKhandelwal/maximum-subarray

Example

console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]));

Output

6

Comments

Post a Comment

Popular posts from this blog

Difference between .exec() and .execPopulate() in Mongoose?

Here I answer what is the difference between .exec() and .execPopulate() in Mongoose? .exec() is used with a query while .execPopulate() is used with a document Syntax for .exec() is as follows: Model.query() . populate ( 'field' ) . exec () // returns promise . then ( function ( document ) { console . log ( document ); }); Syntax for .execPopulate() is as follows: fetchedDocument . populate ( 'field' ) . execPopulate () // returns promise . then ( function ( document ) { console . log ( document ); }); When working with individual document use .execPopulate(), for model query use .exec(). Both returns a promise. One can do without .exec() or .execPopulate() but then has to pass a callback in populate.
1 comment
Read more

Two Ways of rendering in React Examples

Two Ways of rendering in React Examples 1 - Render twice HTML < div id = "p1" ></ div > < div id = "p2" ></ div > CSS . person { display : inline - block ; margin : 10px ; border : 1px solid # eee ; box - shadow : 0 2px 2px # ccc ; } JAVASCRIPT (Babel) function Person ( props ) { return ( < div className = ' person "> < h1 >{ props . name }</ h1 > < p > Age :{ props . age }</ p > </ div > ); } ReactDOM . render (< Person name = "VK" age = "29" />, document . querySselector ( '#p1' )); ReactDOM . render (< Person name = "HK" age = "28" />, document . querySselector ( '#p2' )); 2 Render all at once HTML < div id = "app" ></ div > CSS . person { display : inline - block ; margin : 1...
Post a Comment
Read more

Resolve: Uncaught TypeError: firebase.database is not a function

If you are getting the error: Uncaught TypeError: firebase.database is not a function Resolve it by including firebase-database.js in your html page as follows: <!-- The core Firebase JS SDK is always required and must be listed first --> <script defer src = "https://www.gstatic.com/firebasejs/6.2.4/firebase-app.js" ></script> <script defer src = "https://www.gstatic.com/firebasejs/3.1.0/firebase-database.js" ></script> That is it. Let me know if this was helpful.
Post a Comment
Read more