Problem:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
-Summary-
1. Find the maximum sum by comparing adding previous sum + current index number, and only the current index number.
2. While calculation, we keep comparing those values and update maxAll variable to keep max value only.
Below is the article regarding "Divide and Conquer"
https://www.programiz.com/dsa/divide-and-conquer
Divide and Conquer Algorithm
A divide and conquer algorithm is a strategy of solving a large problem by breaking the problem into smaller sub-problems solving the sub-problems, and combining them to get the desired output. To use divide and conquer algorithms, recursion is used. Learn
www.programiz.com
모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]
'LeetCode > Top Interview Q. - Easy' 카테고리의 다른 글
| LeetCode 5. Valid Parentheses [Strings, Stack] (0) | 2020.06.12 |
|---|---|
| LeetCode. House Robber [Dynamic Programming] (0) | 2020.06.12 |
| LeetCode. Best Time to Buy and Sell Stock [Dynamic Programming] (0) | 2020.06.10 |
| LeetCode. Climbing Stairs [Dynamic Programming] (0) | 2020.06.09 |
| LeetCode. First Bad Version [Sorting and Searching] (0) | 2020.06.08 |
댓글