LeetCode 53: Maximum Subarray

-

Question

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

 A subarray is a contiguous part of an array. 


Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23


Solutions:-

   1) JavaScript      


function maxSubArray(nums) {
  let solution = nums[0];
  for (let i = 1; i < nums.length; i++) {
    nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
    solution = Math.max(solution, nums[i]);
  }
  return solution;
}


2) Go


func Max(x, y int) int {
    if x < y {
        return y
    }
    return x
}
func maxSubArray(nums []int) int {
    solution:=nums[0];
    for i:=1;i<len(nums);i++{
        nums[i]=Max(nums[i],nums[i]+nums[i-1]);
        solution=Max(solution,nums[i])
    }
    return solution;
}


Comments

Post a Comment

Popular posts from this blog

LeetCode 350: Intersection of Two Arrays II

-
Question:-  Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order. Example 1: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Explanation: [9,4] is also accepted. Example 2: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2] Solution:- class Solution {     public int [] intersect ( int [] nums1 , int [] nums2 ) {         int length1 = nums1 . length ;           int length2 = nums2 . length ;         int [] ans = new int [ length1 * length2 ];         int i = 0 , j = 0 , k = 0 ;         Arrays . sort ( nums1 );         Arrays . sort ( nums2 );         while ( i < length1 && j < length2 ){             if ( nums1 [ i ...
Read more

LeetCode 35: Search Insert Position

-
 Question Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with  O(log n)  runtime complexity.   Example 1: Input: nums = [1,3,5,6], target = 5 Output: 2 Example 2: Input: nums = [1,3,5,6], target = 2 Output: 1 Example 3: Input: nums = [1,3,5,6], target = 7 Output: 4   Solution 1- Javascript /** * @param {number[]} nums * @param {number} target * @return {number} */ var searchInsert = function ( nums , target ) { let left = 0 ; let right = nums . length ; while ( left < right ) { const middle = Math . floor (( left + right ) / 2 ); if ( nums [ middle ] < target ) { left = middle + 1 ; } else { right = middle ; } } return left ; };
Read more

LeetCode 217: Contains Duplicate

-
  Question Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct. Example 1: Input: nums = [1,2,3,1] Output: true Example 2: Input: nums = [1,2,3,4] Output: false Example 3: Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true Solutions 1) Go func containsDuplicate ( nums [] int ) bool {     dict := make ( map [ int ] int )     for _ , num := range nums {         dict [ num ]= dict [ num ]+ 1         if ( dict [ num ]> 1 ){             return true ;         }             }     return false } 2) Javascript function containsDuplicate ( nums ) {   const temp = new Set ( nums );   return !( nums . length === temp . size ); }
Read more