longest_convex_subsequence.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0MreRNY5VHXw",
        "outputId": "8e48534a-b670-45be-f6dc-e5b823dc6b5b"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Longest Convex Subsequence: 5\n"
          ]
        }
      ],
      "source": [
        "def longest_convex_subsequence(arr):\n",
        "    n = len(arr)\n",
        "    if n < 3:\n",
        "        return n\n",
        "\n",
        "    max_length = 2\n",
        "\n",
        "    # Iterate through each element as the starting point of a convex subsequence\n",
        "    for i in range(n - 2):\n",
        "        # Initialize the current convex subsequence length to 2\n",
        "        length = 2\n",
        "        prev_diff = arr[i + 1] - arr[i]\n",
        "        # Check all subsequent elements for convexity\n",
        "        for j in range(i + 2, n):\n",
        "            diff = arr[j] - arr[j - 1]\n",
        "            if diff > prev_diff:\n",
        "                # If the difference satisfies the convex condition, increment the length\n",
        "                length += 1\n",
        "                prev_diff = diff\n",
        "        max_length = max(max_length, length)\n",
        "\n",
        "    return max_length\n",
        "sequence = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 7]\n",
        "lis = longest_convex_subsequence(sequence)\n",
        "print(\"Longest Convex Subsequence:\", lis)\n",
        "# Longest Convex Subsequence: 5"
      ]
    }
  ]
}