leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

maximum-subarray.dart (907B)

      1 //Given a list of integers nums find the subarray
      2 //that contains the highest value and return it.
      3 //To do this iterate through nums each time adding to the current
      4 //which is the value of the current subarray. If the subarray drops below 0
      5 //then start a new subarray and continue on. Whenever you have a subarray with a value
      6 //greater than that of the current max set max = current.
      7 //The time complexity of this code is O(n) where n is the length
      8 //of the list nums.
      9 //Concept used: Sliding window
     10 //Time: 340ms Beats: 100%
     11 //Memory: 181.3MB Beats: 49.55%
     12 
     13 class Solution {
     14   int maxSubArray(List<int> nums) {
     15       int max = -1000000;
     16       int current = 0;
     17       for(int i = 0 ; i < nums.length ; ++i){
     18           current += nums[i];
     19           if(current > max){
     20               max = current;
     21           }
     22           if(current < 0){
     23               current = 0;
     24           }
     25       }
     26       return max;
     27   }
     28 }