algos/BiotonicSubarray.cpp at master · punit1009/algos · 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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/*
The Longest Bitonic Subarray (LBS) problem is to find a contiguous subarray of a given sequence in which the subarray’s elements are first sorted in increasing order, then in decreasing order, and the subarray is as long as possible.

Input : [3, 5, 8, 4, 5, 9, 10, 8, 5, 3, 4]
Output: [4, 5, 9, 10, 8, 5, 3]

In case the multiple bitonic subarrays of maximum length exists, the solution can return any one of them.

Input : [-5, -1, 0, 2, 1, 6, 5, 4, 2]
Output: [-5, -1, 0, 2, 1] or [1, 6, 5, 4, 2]
*/

class Solution
{
public:
    vector<int> findBitonicSubarray(vector<int> const &nums)
    {
        // Write your code here...
        int inc = 0;
        int dec = 0;
        int start = 0;
        int end = 0;
        int count = 1;

        vector<int> result;
        int maxLength = 0;
        int maxStart = 0;

        if (nums.size() < 3)
        {
            return nums;
        }

        for (int i = 0; i < nums.size() - 1; i++)
        {
            if (nums[i] < nums[i + 1])
            {
                if (dec == 1)
                {
                    count = 1;
                    dec = 0;
                }
                if (count == 1)
                {
                    start = i;
                    end = 0;
                }

                end = start;
                end++;
                inc = 1;
                count++;
                if (maxLength < count)
                {
                    maxLength = count;
                    maxStart = start;
                }
            }
            else if (nums[i] > nums[i + 1] && inc == 1)
            {
                end++;
                count++;
                if (maxLength < count)
                {
                    maxLength = count;
                    maxStart = start;
                }
                dec = 1;
            }
            else if (nums[i] > nums[i + 1] && inc == 0)
            {
                if (count == 1)
                {
                    start = i;
                    end = 0;
                }
                end = start;
                end++;
                count++;
                if (maxLength < count)
                {
                    maxLength = count;
                    maxStart = start;
                }
                dec = 1;
            }
            else
            {
                start = i;
                count = 1;
                inc = 0;
                dec = 0;
                if (maxLength < count)
                {
                    maxLength = count;
                    maxStart = start;
                }
            }
        }

        for (int i = 0; i < maxLength; i++)
        {
            result.push_back(nums[maxStart + i]);
        }

        return result;
    }
};