Longest Consecutive Temperature Trend — Problem Statement & Solution Guide

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

int longestConsecutiveTemperatureTrend(const vector<int>& temps, const string& pattern){
    int n = temps.size();
    int m = pattern.size();
    if(n==0) return 0;
    // dp[i][k] = longest length ending at i where next expected pattern index is k
    vector<vector<int>> dp(n, vector<int>(m, 1)); // length 1, next expected is 0
    int ans = 1;
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            int rel = (temps[i] > temps[j]) ? 'A' : (temps[i] < temps[j]) ? 'D' : 0;
            if(rel==0) continue; // equal values cannot be used
            for(int k=0;k<m;k++){
                if(rel == pattern[k]){
                    int next = (k+1)%m;
                    dp[i][next] = max(dp[i][next], dp[j][k] + 1);
                    ans = max(ans, dp[i][next]);
                }
            }
        }
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> temps(n);
    for(int i=0;i<n;++i) cin>>temps[i];
    string pattern; cin>>pattern;
    cout<<longestConsecutiveTemperatureTrend(temps, pattern)<<"\n";
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static int longestConsecutiveTemperatureTrend(int[] temps, String pattern){
        int n = temps.length;
        int m = pattern.length();
        if(n==0) return 0;
        int[][] dp = new int[n][m];
        for(int i=0;i<n;i++) Arrays.fill(dp[i],1);
        int ans = 1;
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                char rel = 0;
                if(temps[i] > temps[j]) rel = 'A';
                else if(temps[i] < temps[j]) rel = 'D';
                else continue;
                for(int k=0;k<m;k++){
                    if(rel == pattern.charAt(k)){
                        int nxt = (k+1)%m;
                        dp[i][nxt] = Math.max(dp[i][nxt], dp[j][k] + 1);
                        ans = Math.max(ans, dp[i][nxt]);
                    }
                }
            }
        }
        return ans;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        if(line==null||line.isEmpty()) return;
        int n = Integer.parseInt(line.trim());
        int[] temps = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) temps[i] = Integer.parseInt(st.nextToken());
        String pattern = br.readLine();
        System.out.println(longestConsecutiveTemperatureTrend(temps, pattern));
    }
}

import sys

def longest_consecutive_temperature_trend(temps, pattern):
    n = len(temps)
    m = len(pattern)
    if n == 0:
        return 0
    # dp[i][k] = longest length ending at i where next expected pattern index is k
    dp = [[1]*m for _ in range(n)]
    ans = 1
    for i in range(n):
        for j in range(i):
            if temps[i] > temps[j]:
                rel = 'A'
            elif temps[i] < temps[j]:
                rel = 'D'
            else:
                continue
            for k in range(m):
                if rel == pattern[k]:
                    nxt = (k+1) % m
                    dp[i][nxt] = max(dp[i][nxt], dp[j][k] + 1)
                    ans = max(ans, dp[i][nxt])
    return ans

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    temps = [int(next(it)) for _ in range(n)]
    pattern = next(it) if n>=0 else ''
    print(longest_consecutive_temperature_trend(temps, pattern))

if __name__ == "__main__":
    main()

const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/);
let idx=0;
function longestConsecutiveTemperatureTrend(temps, pattern){
    const n = temps.length;
    const m = pattern.length;
    if(n===0) return 0;
    // dp[i][k] = longest length ending at i where next expected pattern index is k
    const dp = Array.from({length:n},()=>Array(m).fill(1));
    let ans = 1;
    for(let i=0;i<n;i++){
        for(let j=0;j<i;j++){
            let rel = 0;
            if(temps[i] > temps[j]) rel = 'A';
            else if(temps[i] < temps[j]) rel = 'D';
            else continue;
            for(let k=0;k<m;k++){
                if(rel===pattern[k]){
                    const next = (k+1)%m;
                    dp[i][next] = Math.max(dp[i][next], dp[j][k]+1);
                    ans = Math.max(ans, dp[i][next]);
                }
            }
        }
    }
    return ans;
}
let n = parseInt(input[idx++]);
let temps = [];
for(let i=0;i<n;i++) temps.push(parseInt(input[idx++]));
let pattern = input[idx++] || '';
console.log(longestConsecutiveTemperatureTrend(temps, pattern).toString());