We are given an array nums and we need to return the maximum sum of a subarray in nums.
Details
We can employ similar logic in iterative version as well. Here, we again use dp array and use bottom-up approach. Here dp[1][i] denotes maximum subarray sum ending at i (including nums[i]) and dp[0][i] denotes maximum subarray sum upto i (may or may not include nums[i]).
At each index, we update dp[1][i] as max between either only choosing current element - nums[i] or extending from previous subarray and choosing current element as well - dp[1][i-1] + nums[i]
Similarly, dp[0][1] can be updated as max between maximum sum subarray found till last index - dp[0][i-1] or max subarray sum found ending at current index dp[1][i].
problem link :
Summary
We are given an array nums and we need to return the maximum sum of a subarray in nums.
Details
We can employ similar logic in iterative version as well. Here, we again use dp array and use bottom-up approach. Here dp[1][i] denotes maximum subarray sum ending at i (including nums[i]) and dp[0][i] denotes maximum subarray sum upto i (may or may not include nums[i]).
At each index, we update dp[1][i] as max between either only choosing current element - nums[i] or extending from previous subarray and choosing current element as well - dp[1][i-1] + nums[i] Similarly, dp[0][1] can be updated as max between maximum sum subarray found till last index - dp[0][i-1] or max subarray sum found ending at current index dp[1][i].
References
Leetcode
Checks