Koda
Sign UpLog In
Problems
mediumMaximum Sum Increasing Subsequence
5 Koda Coins

Maximum Sum Increasing Subsequence

medium⏱ 2s limit💾 64 MB

Description

Given an array of N positive integers, write a program to find the sum of the maximum sum increasing subsequence (MSIS).


Input Format

  • First line: Integer N.
  • Second line: N space-separated integers.

    • Output Format

  • Print the sum of the maximum sum increasing subsequence.

    • Constraints

  • 1 <= N <= 10^3
  • 1 <= A[i] <= 10^5