Line data    Source code

       1              : // Copyright (c) 2025 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : 
      17              : #include <climits>
      18              : #include <vector>
      19              : 
      20              : #include <gtest/gtest.h>
      21              : 
      22              : namespace {
      23              : class Solution {
      24              : public:
      25            4 :     int maximumDifference(const std::vector<int>& nums) {
      26            4 :         int minidx = 0;
      27            4 :         int max = INT_MIN;
      28          112 :         for (int i = 0; i < nums.size() - 1; ++i) {
      29          108 :             if (nums[minidx] > nums[i]) {
      30           96 :                 minidx = i;
      31              :             }
      32          108 :             max = std::max(max, nums[i + 1] - nums[minidx]);
      33              :         }
      34            4 :         return max <= 0 ? -1 : max;
      35              :     }
      36              : };
      37              : } // namespace
      38              : 
      39            4 : TEST(Leetcode, maximum_difference_between_increasing_elements) {
      40            1 :     Solution s;
      41            1 :     EXPECT_EQ(4, s.maximumDifference({7, 1, 5, 4}));
      42            1 :     EXPECT_EQ(-1, s.maximumDifference({9, 4, 3, 2}));
      43            1 :     EXPECT_EQ(9, s.maximumDifference({1, 5, 2, 10}));
      44            1 :     EXPECT_EQ(-1, s.maximumDifference(
      45              :                       {999, 997, 980, 976, 948, 940, 938, 928, 924, 917, 907, 907, 881, 878, 864,
      46              :                        862, 859, 857, 848, 840, 824, 824, 824, 805, 802, 798, 788, 777, 775, 766,
      47              :                        755, 748, 735, 732, 727, 705, 700, 697, 693, 679, 676, 644, 634, 624, 599,
      48              :                        596, 588, 583, 562, 558, 553, 539, 537, 536, 509, 491, 485, 483, 454, 449,
      49              :                        438, 425, 403, 368, 345, 327, 287, 285, 270, 263, 255, 248, 235, 234, 224,
      50              :                        221, 201, 189, 187, 183, 179, 168, 155, 153, 150, 144, 107, 102, 102, 87,
      51            1 :                        80,  57,  55,  49,  48,  45,  26,  26,  23,  15}));
      52            1 : }