commit 7691cbf6e7e0b6de223124d8e37e332c6b249c7b parent 40a4658350b8e8408405debf1d6615f9c94a5035 Author: AndrewLockVI <andrewlaack1@gmail.com> Date: Sun, 28 May 2023 16:03:48 -0500 Completed maximum subarray using dart and sliding window techniqueg Diffstat:
| A | maximum-subarray/maximum-subarray.dart | | | 28 | ++++++++++++++++++++++++++++ |
1 file changed, 28 insertions(+), 0 deletions(-)
diff --git a/maximum-subarray/maximum-subarray.dart b/maximum-subarray/maximum-subarray.dart @@ -0,0 +1,28 @@ +//Given a list of integers nums find the subarray +//that contains the highest value and return it. +//To do this iterate through nums each time adding to the current +//which is the value of the current subarray. If the subarray drops below 0 +//then start a new subarray and continue on. Whenever you have a subarray with a value +//greater than that of the current max set max = current. +//The time complexity of this code is O(n) where n is the length +//of the list nums. +//Concept used: Sliding window +//Time: 340ms Beats: 100% +//Memory: 181.3MB Beats: 49.55% + +class Solution { + int maxSubArray(List<int> nums) { + int max = -1000000; + int current = 0; + for(int i = 0 ; i < nums.length ; ++i){ + current += nums[i]; + if(current > max){ + max = current; + } + if(current < 0){ + current = 0; + } + } + return max; + } +}