Longest Alternating Sequences — Problem Statement & Solution Guide

#include <bits/stdc++.h>
using namespace std;

pair<int,int> longestAlternatingSequences(const vector<int>& values) {
    if(values.empty()) return {0,0};
    int n = values.size();
    // inc[i] = length of strictly increasing run ending at i
    // dec[i] = length of strictly decreasing run ending at i
    vector<int> inc(n,1), dec(n,1);
    for(int i=1;i<n;++i){
        if(values[i]>values[i-1]) inc[i]=inc[i-1]+1;
        if(values[i]<values[i-1]) dec[i]=dec[i-1]+1;
    }
    int maxUpDown = 1, maxDownUp = 1;
    // Up‑Down: increasing then decreasing. The peak is at position i.
    for(int i=0;i<n;++i){
        // length = inc[i] + dec[i] - 1 (peak counted twice)
        int len = inc[i] + dec[i] - 1;
        maxUpDown = max(maxUpDown, len);
    }
    // Down‑Up: decreasing then increasing. The valley is at position i.
    // We can reuse inc and dec by swapping roles.
    // Compute incFromLeft (already) and decFromLeft (already). For valley we need decreasing run ending at i and increasing run starting at i.
    // Compute incFromRight.
    vector<int> incR(n,1);
    for(int i=n-2;i>=0;--i){
        if(values[i]<values[i+1]) incR[i]=incR[i+1]+1;
    }
    for(int i=0;i<n;++i){
        int len = dec[i] + incR[i] - 1;
        maxDownUp = max(maxDownUp, len);
    }
    return {maxUpDown, maxDownUp};
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> a(n);
    for(int i=0;i<n;++i) cin>>a[i];
    auto ans = longestAlternatingSequences(a);
    cout << ans.first << " " << ans.second << "\n";
    return 0;
}

import java.util.*;

public class Main {
    // Returns [maxUpDown, maxDownUp]
    public static int[] longestAlternatingSequences(int[] values) {
        if (values.length == 0) return new int[]{0, 0};
        int n = values.length;
        int[] inc = new int[n]; // increasing run ending at i
        int[] dec = new int[n]; // decreasing run ending at i
        Arrays.fill(inc, 1);
        Arrays.fill(dec, 1);
        for (int i = 1; i < n; i++) {
            if (values[i] > values[i - 1]) inc[i] = inc[i - 1] + 1;
            if (values[i] < values[i - 1]) dec[i] = dec[i - 1] + 1;
        }
        int maxUpDown = 1;
        for (int i = 0; i < n; i++) {
            int len = inc[i] + dec[i] - 1; // peak at i
            if (len > maxUpDown) maxUpDown = len;
        }
        // increasing run from right for down‑up
        int[] incR = new int[n];
        Arrays.fill(incR, 1);
        for (int i = n - 2; i >= 0; i--) {
            if (values[i] < values[i + 1]) incR[i] = incR[i + 1] + 1;
        }
        int maxDownUp = 1;
        for (int i = 0; i < n; i++) {
            int len = dec[i] + incR[i] - 1; // valley at i
            if (len > maxDownUp) maxDownUp = len;
        }
        return new int[]{maxUpDown, maxDownUp};
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.hasNextInt() ? sc.nextInt() : 0;
        int[] values = new int[n];
        for (int i = 0; i < n; i++) values[i] = sc.nextInt();
        int[] ans = longestAlternatingSequences(values);
        System.out.println(ans[0] + " " + ans[1]);
    }
}

def longestAlternatingSequences(values):
    if not values:
        return (0, 0)
    n = len(values)
    inc = [1] * n  # increasing run ending at i
    dec = [1] * n  # decreasing run ending at i
    for i in range(1, n):
        if values[i] > values[i - 1]:
            inc[i] = inc[i - 1] + 1
        if values[i] < values[i - 1]:
            dec[i] = dec[i - 1] + 1
    max_up_down = 1
    for i in range(n):
        length = inc[i] + dec[i] - 1  # peak at i
        if length > max_up_down:
            max_up_down = length
    # increasing run from the right for down‑up
    inc_r = [1] * n
    for i in range(n - 2, -1, -1):
        if values[i] < values[i + 1]:
            inc_r[i] = inc_r[i + 1] + 1
    max_down_up = 1
    for i in range(n):
        length = dec[i] + inc_r[i] - 1  # valley at i
        if length > max_down_up:
            max_down_up = length
    return (max_up_down, max_down_up)

if __name__ == "__main__":
    import sys
    data = sys.stdin.read().strip().split()
    if not data:
        print("0 0")
        sys.exit()
    n = int(data[0])
    values = list(map(int, data[1:1 + n]))
    up, down = longestAlternatingSequences(values)
    print(up, down)

function longestAlternatingSequences(values) {
    if (values.length === 0) return [0, 0];
    const n = values.length;
    const inc = new Array(n).fill(1);
    const dec = new Array(n).fill(1);
    for (let i = 1; i < n; ++i) {
        if (values[i] > values[i - 1]) inc[i] = inc[i - 1] + 1;
        if (values[i] < values[i - 1]) dec[i] = dec[i - 1] + 1;
    }
    let maxUpDown = 1, maxDownUp = 1;
    for (let i = 0; i < n; ++i) {
        const len = inc[i] + dec[i] - 1; // peak at i
        if (len > maxUpDown) maxUpDown = len;
    }
    // compute increasing run from right for down‑up
    const incR = new Array(n).fill(1);
    for (let i = n - 2; i >= 0; --i) {
        if (values[i] < values[i + 1]) incR[i] = incR[i + 1] + 1;
    }
    for (let i = 0; i < n; ++i) {
        const len = dec[i] + incR[i] - 1; // valley at i
        if (len > maxDownUp) maxDownUp = len;
    }
    return [maxUpDown, maxDownUp];
}

const readline = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});
let lines = [];
readline.on('line', line => lines.push(line.trim()));
readline.on('close', () => {
    const n = parseInt(lines[0] || '0', 10);
    const values = (lines[1] || '').split(/\s+/).filter(s=>s.length).map(Number);
    const [upDown, downUp] = longestAlternatingSequences(values);
    console.log(upDown + ' ' + downUp);
});