Description:
https://leetcode.com/problems/maximum-product-of-three-numbers/description/
Code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
class Solution { public: int maximumProduct(vector<int>& nums) { int large1 = INT_MIN, large2 = INT_MIN, large3 = INT_MIN; int small1 = INT_MAX, small2 = INT_MAX; for (int i = 0; i < nums.size(); i++) { if (nums[i] > large3) { if (nums[i] > large2) { if(nums[i] > large1) { large3 = large2; large2 = large1; large1 = nums[i]; } else { large3 = large2; large2 = nums[i]; } } else { large3 = nums[i]; } } if (nums[i] < small2) { if (nums[i] < small1) { small2 = small1; small1 = nums[i]; } else { small2 = nums[i]; } } } int largeNum1 = large3 * large2 * large1; int largeNum2 = large1 * small1 * small2; return largeNum1 > largeNum2 ? largeNum1 : largeNum2; } }; |
Time & Space:
O(n) & O(1)