53. Maximum Subarray

문제 설명

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.

정수 배열 nums가 주어질때 연속된 합의 값이 가장 큰것을 찾는 문제이다.

Example

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

Idea

for문을 돌며 배열의 인덱스 값에 해당하는 인덱스 값 또는 이전 값을 더한 값중 더 큰 값으로 바꿔준뒤 가장 큰값을 리턴 해준다.

Solution

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)
};