Kolokwium__Algorytmy do Zad4.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

namespace Kolokwium2_TeoriaAlgorytmów
{
    class Program
    {
        public static void hoteleTrasa(int[] trasa, int rr)
        {
            if (rr > 0)
            {
                hoteleTrasa(trasa, trasa[rr]);
            }

            Console.Write(rr + " ");
        } //pomocnicza funkcja do zadania 2.
        public static bool dict(char[] s, int p, int k)
        {
            string tmp = "";
            for (int i = p; i <= k; i++)
            {
                 tmp = tmp + s.ElementAt(i);
            }
            string[] dictionary = {"jesteśmy", "najlepsi", "wśród", "najlepszych"};
            return dictionary.Contains(tmp);

        } //pomocnicza funkcja do zadania 4(TU UZUPEŁNIĆ POPRAWNYMI SŁÓWKAMI)
        static void Main(string[] args)
        {
            /*
            int[] a = {-5,7,3,-10,12,-8,5,9};
            Zadanie1(a);
            Console.ReadKey();
            */
            /*
            int[] b = {280,461,490,542,759,786,883};
            Zadanie2(b);
            Console.ReadKey();
            */
            /*
            int[] m = {117, 181, 298, 396, 432, 454, 610, 627, 680, 774};
            int[] p = {14, 20, 9, 19, 18, 11, 8, 14, 16, 5};
            Zadanie3(m,p,130);
            Console.ReadKey();
            */
            /*
            string s = "najlepsiwśródnajlepszych"; //Tutaj musiałem zmienic wejściowego stringa(wśród zamiast z). program nie działa z
                                                //jednoznakowymi stringami jak "z / w / u"
            char[] ss = s.ToCharArray();
            Zadanie4(ss);
            Console.ReadKey();
            */



        }
        //Programowanie Dynamiczne Ćw8.
        static void Zadanie1(int[] a) //podciąg spójny o mozliwie najwiekszej sumie (Kroki: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/)
        {
            int size = a.Length;
            int max_so_far = int.MinValue,
                max_ending_here = 0;
            int s = 0;
            int start = 0;
            int end = 0;

            for (int i = 0; i < size; i++)
            {
                max_ending_here = max_ending_here + a[i];

                if (max_so_far < max_ending_here)
                {
                    max_so_far = max_ending_here;
                    start = s;
                    end = i;
                }

                if (max_ending_here < 0)
                {
                    max_ending_here = 0;
                    s = i + 1;
                }
            }

            Console.Write("Najwiekszym podciągiem spójnym o najwiekszej sumie jest podciąg: ");
            for (int i = start; i <= end; i++)
            {
                Console.Write(a[i] + ",");
            }
            Console.Write(" o sumie: "+max_so_far);
        }

        static void Zadanie2(int[] b) //Algorytm efektywnego wyznaczania ciągu hoteli w podrózy z karą
        {
            int[] kara = new int[b.Length];
            int[] trasa = new int[b.Length];
            kara[0] = 0;
            kara[1] = (int) Math.Pow(200 - b[1], 2);
            trasa[0] = trasa[1] = 0;

            for (int i = 2; i < b.Length; i++)
            {
                kara[i] = -1000;
                trasa[i] = -1;
            }

            for (int j = 2; j < b.Length; j++)
            {
                for (int d = 0; d < j; d++)
                {
                    int tmp = (int)(Math.Pow(200 - (b[j] - b[d]),2)+kara[d]);
                    if (tmp < kara[j])
                    {
                        kara[j] = tmp;
                        trasa[j] = d;
                    }
                    else if(kara[j] == -1000)
                    {
                        kara[j] = tmp;
                        trasa[j] = d;
                    }
                }
            }

            for (int i = 1; i < b.Length; i++)
            {
                Console.WriteLine("Hotel w odległości: " + b[i] + ", kara wynosi: " + kara[i] +
                                  ". Optymalna trasa przez podane hotele to: ");
                hoteleTrasa(trasa,i);
                Console.WriteLine();
            }

        }

        static void Zadanie3(int[] m, int[] p, int k) //Algorytm maksymalnego oczekiwanego całkowitego zysku
        {
            int[] P = new int[m.Length];
            int temp = 0;
            int mnoznik = 0;
            for (int a = 1; a < m.Length; a++)
            {

                for (int b = 0; b <= a - 1; b++)
                {
                    if (m[a] - m[b] < k)
                    {
                         mnoznik = 0;
                    }
                    else if (m[a] - m[b] >= k)
                    {
                         mnoznik = 1;
                    }

                    temp = P[b] + (mnoznik * p[a]);

                    if (temp > P[a])
                    {
                        P[a] = temp;
                    }
                }

                if (P[a] < p[a])
                {
                    P[a] = p[a];
                }
            }

            Console.WriteLine("Przewidywany optymalny zysk to :"+P.Max());

        }

        static void
            Zadanie4(char[] s) //Algorytm wypisujący pojedyncze słowa ze złączonego zdania. Trzeba uzupełnic słownik u góry
        {
            int[] R = new int[s.Length];
            for (int i = 0; i < s.Length; i++)
            {
                R[i] = 0;
                for (int j = 0; j <= i - 1; j++)
                {
                    if (dict(s, j, i) == true)
                    {
                        R[j] = 1;
                    }
                }
            }

            for (int i = 0; i < s.Length; i++)
            {
                if (R[i] == 1)
                {
                    Console.Write(" ");
                }

                Console.Write(s[i]);
            }
        }
    }
}