leetcodesolutions/code/1911.maximum-alternating-subsequence-sum.java at main · Raghuram42/leetcodesolutions · GitHub

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
48
49
50
51
52
53
54
class Solution {
    public long maxAlternatingSum(int[] nums) {
        Stack<Integer> stk = new Stack<>();
        stk.push(nums[0]);
        int i = 1;

        while(i<nums.length){

            if(stk.size() >0 && stk.size()%2 == 1){
            while(stk.size() > 0 && stk.size()%2 == 1 && stk.peek() <= nums[i])
                stk.pop();
            }else{
                while(stk.size() > 0 && stk.size()%2 == 0 && stk.peek() > nums[i])
                stk.pop();

            }

            stk.push(nums[i++]);

        }


        if(stk.size()%2 == 0 && stk.size() > 0)
            stk.pop();


        long res = 0;

        while(!stk.isEmpty()){
            if(stk.size()%2 == 0)
                res -= stk.pop();
            else
                res+=stk.pop();

        }

        return res;

    }
}
/*
[4,2,5,3]
[5,6,7,8]
[6,2,1,2,4,5]
[4,5,4,5]
[4,6,6,2,3]
[6,6,6,2,3]
[7,6,6,2,3]
[7,6,6,10,3]
[7,6,6,10,3,4]
[1]
[1,90]
[90,1]
*/