Question
The array that contains the only integer is given. The integer might be positive and negative as well. You need to find the sub-array that has the biggest sum in the array. As you know, the sub-array means that the array is a subsequence.
Solution
I prepared an array that has a length of two at first. In the array, the first value is supposed to be stored current maximum value at that time. Also, the second value in the array is to be stored as the current maximum of the sum of the subarray.
I explore from the left of the given array by each element. And then, compare the current value of the element and the second value of the array that added the current value, and then update the bigger value. And then, compare with the current maximum and updated the value. then update the bigger one. You will repeat this operation until the end of the array.
In the end, return the first element of the array. That is the answer.
Submission
This is the result of my code.
Runtime: 68 ms, faster than 58.02% of Python3 online submissions for Maximum Subarray.
Memory Usage: 14.7 MB, less than 5.69% of Python3 online submissions for Maximum Subarray.
Time complexity: O(n)
Space complexity: O(1)
Each element is checked once in sequence. So time complexity becomes O(n). I defined one array that has the length of two regardless of the length of the given array. So, this is constant. Time complexity is gonna be O(1).
Here is my python code.
def maxSubArray(self, nums: List[int]) -> int:
arr: List[int] = [nums[0], nums[0]]
for n in nums[1:]:
arr[1] = max(n, n + arr[1])
arr[0] = max(arr[0], arr[1])
return arr[0]
https://github.com/nk18chi/leetcode/blob/master/solutions/maximum_subarray/index.py
