Online Courses
Free Tutorials  Go to Your University  Placement Preparation 
0 like 0 dislike
1.2k views
in Coding Questions by Goeduhub's Expert (2.3k points)

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

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.

 

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 = [0]
Output: 0

Example 4:

Input: nums = [-1]
Output: -1

Example 5:

Input: nums = [-2147483647]
Output: -2147483647

 

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -231 <= nums[i] <= 231 - 1

Goeduhub's Top Online Courses @Udemy

For Indian Students- INR 360/- || For International Students- $9.99/-

S.No.

Course Name

 Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence || Labeled as Highest Rated Course by Udemy

Apply Coupon

2.

Complete Machine Learning & Data Science with Python| ML A-Z Apply Coupon

3.

Complete Python Programming from scratch | Python Projects Apply Coupon
    More Courses

1 Answer

0 like 0 dislike
by Goeduhub's Expert (2.3k points)
 
Best answer

Apparently, this is a optimization problem, which can be usually solved by DP. So when it comes to DP, the first thing for us to figure out is the format of the sub problem(or the state of each sub problem). The format of the sub problem can be helpful when we are trying to come up with the recursive relation.

At first, I think the sub problem should look like: maxSubArray(int A[], int i, int j), which means the maxSubArray for A[i: j]. In this way, our goal is to figure out what maxSubArray(A, 0, A.length - 1) is. However, if we define the format of the sub problem in this way, it's hard to find the connection from the sub problem to the original problem(at least for me). In other words, I can't find a way to divided the original problem into the sub problems and use the solutions of the sub problems to somehow create the solution of the original one.

So I change the format of the sub problem into something like: maxSubArray(int A[], int i), which means the maxSubArray for A[0:i ] which must has A[i] as the end element. Note that now the sub problem's format is less flexible and less powerful than the previous one because there's a limitation that A[i] should be contained in that sequence and we have to keep track of each solution of the sub problem to update the global optimal value. However, now the connect between the sub problem & the original one becomes clearer:

maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i]; 
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        dp = [float("-inf")] * (len(nums) + 1)
        dp[0] = nums[0]
        self.findSubarray(nums, len(nums) - 1, dp)
        return max(dp)
        
    def findSubarray(self, nums, i, dp):
        if i == 0:
            return dp[0]
        
        dp[i] = max(nums[i], nums[i] + self.findSubarray(nums, i - 1, dp))
        return dp[i]

eg : ans = Solution()

ans.maxSubArray([-2,1,-3,4,-1,2,1,-5,4])

Output -

6

3.3k questions

7.1k answers

394 comments

4.6k users

Related questions

0 like 0 dislike
1 answer 759 views
0 like 0 dislike
1 answer 973 views
asked Sep 14, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 289 views
asked Sep 4, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 673 views
0 like 0 dislike
1 answer 120 views

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...