[LeetCode/Easy] 2016. Maximum Difference Between Increasing Elements

1. Input

1) 정수 배열 nums

 

2. Output

1) i<j이고 nums[i]<nums[j]인 쌍들 중에 두 요소의 차가 가장 큰 것을 찾아 그 값을 반환

2) 만약 위 조건을 만족하는 쌍이 없다면 -1을 반환

 

3. Constraint

1) 2 <= nums.length <= 1000

2) 1 <= nums[i] <= 10^9

 

4. Example

Input: nums = [7,1,5,4] -> Output: 4

Input: nums = [9,4,3,2] -> Output: -1

설명:

- i<j이고 nums[i]<nums[j]인 쌍은 (1,5), (1,4)가 있으며, 각 쌍의 요소들 간의 차는 4, 3이므로 4를 반환한다.

- i<j이고 nums[i]<nums[j]인 쌍이 없으므로 -1을 반환한다.

 

5. Code

1) 첫 코드(2022/07/13)

int dif = -1;
for(int i=0 ; i<nums.length-1 ; i++){
    if(nums[i]<nums[i+1]){
        int n = nums[i+1];
        for(int j=i+2 ; j<nums.length ; j++){
            if(n<nums[j])
                n = nums[j];
        }
        if(dif<n-nums[i]) dif = n - nums[i];
    }
} // for i

return dif;

2) 간단하게 바꾼 코드(2023/01/11)

int dif = -1;
for(int i=0 ; i<nums.length-1 ; i++){
    for(int j=i+1 ; j<nums.length ; j++){
        if(nums[i]<nums[j])
            dif = nums[j]-nums[i]>dif ? nums[j]-nums[i] : dif;
    }
} // for i

return dif;

- 변수는 1개 덜 사용해서 메모리 사용량은 줄였지만, i<j에서 nums[i]<nums[j]인 모든 nums[j]에서 dif를 계산하기 때문에 속도는 더 느렸다.