using System;

using System.Collections.Generic;

public class Program

{

    //http://practice.geeksforgeeks.org/problems/maximum-sum-increasing-subsequence/0

    //http://www.geeksforgeeks.org/printing-maximum-sum-increasing-subsequence/

    //http://www.geeksforgeeks.org/dynamic-programming-set-14-maximum-sum-increasing-subsequence/

    //!if max sum!!!!!

    public static void Main()

    {

        int[] array =  {1, 101, 2, 3, 100, 4, 5};

        int maxSum = FindMaxSumOfIncreasing(array);

        Console.WriteLine(maxSum);

        int maxSum1 = MSIS(array);

        Console.WriteLine(maxSum1);

    }

    public static int FindMaxSumOfIncreasing(int[] ar)

    {

        int n = ar.Length;

        int[] msis = new int[n];

        for(int i = 0; i < n; i++)

        {

            msis[i] = ar[i];

        }

        for(int i = 1; i < n; i++)

        {

            for(int j = 0 ; j < i  ; j++)

            {

                if (ar[j] < ar[i] && msis[i] < msis[j] + ar[i])

                {

                    msis[i] = msis[j] + ar[i];

                }

            }

        }

        int max = -1;

        for(int i = 0;  i < n; i++)

        {

            if (msis[i] > max)

            {

                max = msis[i];

            }

        }

        return max;

    }   

    public static int MSIS(int[] arr)

    {

        int n = arr.Length;

        if (n == 1)

        {

            return arr[0];

        }

        int[] msis = new int[n];

        for(int i =0; i < n; i++)

        {

            msis[i] = arr[i];

        }

        int max = msis[0];

        for(int j = 1; j < n; j++)

        {

            for(int i = 0; i < j; i++)

            {

                if (arr[j] > arr[i] && msis[j] < msis[i] + arr[j])

                {

                    msis[j] = msis[i] + arr[j];                 

                    if (max < msis[j])

                    {

                        max = msis[j];

                    }

                }

            }           

        }

        return max;

    }

}