leetcode

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

maximum-product-subarray.dart (981B)

      1 //Find the maximum subarray of a list where the product of the subarray is the greatest.
      2 //I used a brute force solution to iterate through the list and find the max subarray of each
      3 //value and then returned the highest total max subarray.
      4 //This solution is O(n^2) time complexity where n is the number of values in the list.
      5 //Time: 290ms Beats: 66.67%
      6 //Memory: 144MB BeatsY 66.67%
      7 class Solution {
      8   int maxProduct(List<int> nums) {
      9       int max = nums[0];
     10       for(int i = 0 ; i < nums.length - 1 ; ++i){
     11           if(nums[i] > max){
     12               max = nums[i];
     13           }
     14           int current = nums[i];
     15           for(int x = i + 1; x < nums.length ; ++ x){
     16             current = nums[x] * current;
     17             if(current > max){
     18                 max = current;
     19             }
     20             if(current == 0){
     21                 break;
     22             }
     23         }
     24       }
     25       if(nums[nums.length - 1] > max){
     26           return nums[nums.length-1];
     27       }
     28       return max;
     29   }
     30 }