#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<initializer_list>
#include"topdown.h"


template<class T>
class Matrix
{
	template<class T>
	using matrix_initializer_list = std::initializer_list<std::initializer_list<T>>;

	std::vector<T> values;
	size_t n, m;

	/* позволява следните извиквания:
	 * Matrix<int> m1{ {1,2,3}, {4,5,6} };
	 * Matrix<int> m2 = { {1,2,3}, {4,5,6} };
	 * void f(Matrix<int>);
	 * f({ {1,2,3}, {4,5,6} });
	 */
	void init(const matrix_initializer_list<T>& il)
	{
		clear();
		n = il.size();
		m = il.begin()->size();
		for (const auto& row : il) if (row.size() != m)
		{
			std::cout << "Invalid matrix dimensions (jagged matrix)!\n";
			clear();
			return;
		}
		values.resize(n*m);
		size_t idx = 0;
		for (const auto& row : il)
			for (const auto& val : row)
				values[idx++] = val; // така е малко по-приятно ^^
	}
	void clear() noexcept
	{
		values.clear();
		n = m = 0;
	}
public:
	Matrix(size_t _n, size_t _m, const T& _val = T()) : values(_n*_m, _val), n(_n), m(_m) {}
	Matrix(const matrix_initializer_list<T>& il) { init(il); }
	Matrix& operator=(const matrix_initializer_list<T>& il) { init(il); return *this; }

	T* operator[](size_t row) { return values.data() + m*row; }
	const T* operator[](size_t row) const { return values.data() + m*row; }
	T at(size_t i, size_t j) const noexcept(noexcept(T()))
	{
		// exception-safe версия на оператора [], която връща
		// стойност по подразбиране при невалидни индекси
		if (i >= n || j >= m) return T();
		return (*this)[i][j];
	}
	size_t rows() const noexcept { return n; }
	size_t cols() const noexcept { return m; }
};

template<class T>
std::ostream& operator<<(std::ostream& os, const Matrix<T>& matr)
{
	for (size_t i = 0; i < matr.rows(); i++)
	{
		for (size_t j = 0; j < matr.cols(); j++) os << matr[i][j] << " ";
		os << "\n";
	}
	return os << "\n";
}

void minimumCoinCount(const std::vector<size_t>& coins, const size_t S) // T(n,S) = O(nS), M(n,S) = O(S)
{
	std::vector<size_t> M(S + 1, std::numeric_limits<size_t>::max());
	M[0] = 0;
	for (size_t x = 1; x <= S; x++)
		for (auto c : coins)
			if (c <= x) M[x] = std::min(M[x], M[x - c] + 1);
	// return M[S];

	if (M[S] == std::numeric_limits<size_t>::max())
	{
		std::cout << "It's impossible to gather the selected sum with these coins!\n";
		return;
	}
	std::cout << "S = " << S << " with coins:";
	for (auto c : coins) std::cout << " " << c;
	std::cout << "\nMinimum coin count is " << M[S] << ":";
	size_t sum = S;
	while (sum)
	{
		for (size_t i = 0; i < coins.size(); i++) if (M[sum] == M[sum - coins[i]] + 1)
		{
			std::cout << " " << coins[i];
			sum -= coins[i];
			break;
		}
	}
	std::cout << "\n\n";
}

void binomialCoefficient(const size_t n, const size_t k) // T(n,k) = O(nk), M(n,k) = O(nk) <- може да се оптимизира до M(n,k) = O(k)
{
	Matrix<size_t> M(n, k, 0);
	for (size_t i = 0; i < k; i++) M[i][i] = 1;
	for (size_t i = 0; i < n; i++) M[i][0] = i + 1;

	for (size_t i = 1; i < n; i++)
		for (size_t j = 1; j < k && j < i; j++)
			M[i][j] = M[i - 1][j - 1] + M[i - 1][j];
	//return M[n - 1][k - 1];
	std::cout << n << " over " << k << " = " << M[n - 1][k - 1] << "\n\n";
}

void longestIncreasingSubsequence(const std::vector<int>& values) // T(n) = O(n^2), M(n) = O(n)
{
	/* забележка:
	 * с изграждането на граф отново T(n) = O(n^2), но M(n) = O(n+m) - изграждането винаги е бавно и ни трябва допълн. памет
	 * без построяване на граф T(n) = O(n^2), но M(n) = O(n)
	 */
	const size_t count = values.size();
	std::vector<size_t> M(count), successors(count);
	for (size_t i = count - 1; i < count; i--) // i < count вместо i>=0
	{
		M[i] = 1;
		successors[i] = count;
		for (size_t j = i + 1; j < count; j++)
			if (values[i] < values[j] && M[i] < M[j] + 1)
			{
				M[i] = M[j] + 1;
				successors[i] = j;
			}
	}
	size_t maxIdx = 0;
	for (size_t i = 1; i < M.size(); i++) if (M[maxIdx] < M[i]) maxIdx = i;
	//return M[maxIdx];

	std::cout << "Longest increasing subsequence:";
	size_t nextIdx = maxIdx;
	while (nextIdx != count)
	{
		std::cout << " " << values[nextIdx];
		nextIdx = successors[nextIdx];
	}
	std::cout << "\nLength = " << M[maxIdx] << "\n\n";
}

void optimalSingleRobotPath(const Matrix<int>& field) // T(n,m) = O(nm), M(n,m) = O(nm) <- може да се оптимизира до M(n,m) = O(min{n,m})
{
	const size_t n = field.rows(), m = field.cols();
	Matrix<int> M(n, m, std::numeric_limits<int>::min());
	M[n - 1][m - 1] = field[n - 1][m - 1];
	for (size_t i = n - 2; i < n; i--) M[i][m - 1] = M[i + 1][m - 1] + field[i][m - 1];
	for (size_t j = m - 2; j < m; j--) M[n - 1][j] = M[n - 1][j + 1] + field[n - 1][j];
	
	for (size_t i = n - 2; i < n; i--)
		for (size_t j = m - 2; j < m; j--)
		{
			M[i][j] = std::max(M[i][j], M[i + 1][j] + field[i][j]);
			M[i][j] = std::max(M[i][j], M[i][j + 1] + field[i][j]);
		}
	//return M[0][0];
	
	std::cout << field;
	std::cout << "Maximum profit path:";
	size_t i = 0, j = 0;
	while (i < n - 1 || j < m - 1)
	{
		if (i < n - 1 && M[i][j] == M[i + 1][j] + field[i][j]) { std::cout << " D"; ++i; continue; }
		if (j < m - 1 && M[i][j] == M[i][j + 1] + field[i][j]) { std::cout << " R"; ++j; continue; }
	}
	std::cout << "\nMaximum profit: " << M[0][0] << "\n\n";
}

void nDigitIntegerCount(const size_t n, const size_t S) // T(n,S) = O(nS), M(n,S) = O(nS) <- може да се оптимизира до M(n,S) = O(S)
{
	Matrix<size_t> M(n, S + 1, 0);
	for (size_t i = 1; i < n; i++) M[i][0] = 0;
	for (size_t j = 0; j < 10; j++) M[0][j] = 1;
	for (size_t j = 10; j <= S; j++) M[0][j] = 0;

	for (size_t k = 1; k < n; k++)
		for (size_t P = 1; P <= S; P++)
			for (size_t i = 0; i < 10; i++)
				M[k][P] += M.at(k - 1, P - i);
	// M[n-1][S] ако се позволени водещи нули; M[n-1][S] - M[n-2][S] ако не са позволени
	std::cout << "The number of " << n << "-digit numbers with digit sum " << S << " is " << M[n - 1][S] - M.at(n - 2, S) << ".\n\n";
}

// всеки "предмет" за задачата за раницата е наредена двойка, в която
// първият елемент е теглото, а вторият елемент е цената му
using Item = std::pair<size_t, size_t>;
void Knapsack(const std::vector<Item>& items, const size_t W) // Т(n,W) = O(nW), M(n,W) = O(W)
{
	std::vector<size_t> M(W + 1, 0);
	for (size_t w = 1; w <= W; w++)
		for (const auto& item : items)
		{
			if (item.first <= w)
				M[w] = std::max(M[w], M[w - item.first] + item.second);
		}
	//return M[W];

	std::cout << "The optimal profit for weight " << W << " is: " << M[W] << "\nThe following items are being used:\n";
	size_t w = W;
	while (M[w] != 0)
	{
		for(const auto& item : items)
			if (item.first <= w && M[w] == M[w - item.first] + item.second)
			{
				std::cout << "  W: " << item.first << " C: " << item.second << "\n";
				w -= item.first;
				break;
			}
	}
	std::cout << "The unused space in the knapsack is: " << w << ".\n\n";
}

void KnapsackNoRepetitions(const std::vector<Item>& items, const size_t W) // T(n,W) = O(nW), M(n,W) = O(nW) <- може да се оптимизира до M(n,W) = O(W)
{
	const size_t n = items.size();
	Matrix<size_t> M(n + 1, W + 1, 0);
	for (size_t k = 1; k <= n; k++)
		for (size_t P = 1; P <= W; P++)
		{
			const auto& item = items[k - 1];
			if (item.first > P)
				M[k][P] = M[k - 1][P];
			else
				M[k][P] = std::max(M[k - 1][P], M[k - 1][P - item.first] + item.second);
		}
	//return M[n][W]

	std::cout << "The optimal profit for weight " << W << " is: " << M[n][W] << "\nThe following items are being used:\n";
	size_t P = W;
	for (size_t k = n; k != 0;k--) if (M[k][P] != M[k - 1][P])
	{
		const auto& item = items[k - 1];
		std::cout << "  W: " << item.first << " C: " << item.second << "\n";
		P -= item.first;
	}
	std::cout << "The unused space in the knapsack is: " << P << ".\n\n";
}

void Partition(const std::vector<int>& values) // T(n) = O(nS), M(n) = O(nS) <- може да се оптимизира до M(n) = O(S)
{
	int S = 0;
	for (auto v : values) S += v;
	if (S % 2 == 1)
	{
		std::cout << "There is no possible partition for a multiset with odd sum!\n\n";
		return;
	}
	S /= 2;
	const size_t n = values.size();
	// налага се да симулираме bool чрез int - иначе трябва кодът на Matrix да се
	// допълни и промени до неузнаваемост, за да работи като std::vector<bool> :(
	Matrix<int> M(n, S + 1, 0);
	for (size_t P = 1; P <= S; P++)
		M[0][P] = (P == 0) || (P == values[0]);
	for (size_t i = 1; i < n; i++)
		for (size_t P = 0; P <= S; P++)
			if (values[i] > P)
				M[i][P] = M[i - 1][P];
			else
				M[i][P] = M[i - 1][P] || M[i - 1][P - values[i]];
	// return bool(M[n - 1][S]);

	if (!M[n - 1][S])
	{
		std::cout << "There is no possible partition for the multiset\n";
		for (auto v : values) std::cout<< v << " ";
		std::cout << "\n\n";
		return;
	}
	std::cout << "One possible partition for the multiset\n";
	for (auto v : values) std::cout << v << " ";
	std::cout << "is:\n";
	size_t P = S;
	for (size_t k = n - 1; k < n; k--)
	{
		if ((P >= values[k] && M[k - 1][P - values[k]]) || (k == 0 && M[0][P]))
		{
			std::cout << values[k] << " ";
			P -= values[k];
		}
	}
	std::cout << "\n\n";
}

void maximumSubarraySum(const std::vector<int>& values, int* result = nullptr, size_t* from = nullptr, size_t* to = nullptr) // T(n) = O(n), M(n) = O(1)
{
	size_t first = 0;
	while (first < values.size() && values[first] < 0) ++first;

	size_t bestFrom = first, bestTo = first, currFrom = first;
	int current = values[first], best = values[first];
	if (first == values.size())
	{
		best = values[0];
		bestFrom = 0;
		for (size_t i = 1; i < values.size(); i++) if (values[i] > best)
		{
			best = values[i];
			bestFrom = i;
		}
		bestTo = bestFrom;
	}
	else for (size_t i = first + 1; i < values.size(); i++)
	{
		current += values[i];
		if (current < 0)
		{
			current = 0;
			currFrom = i + 1;
		}
		if (current > best)
		{
			best = current;
			bestFrom = currFrom;
			bestTo = i;
		}
	}

	if (result == nullptr && from == nullptr && to == nullptr)
	{
		std::cout << "The maximum subarray sum for the array";
		for (auto v : values) std::cout << " " << v;
		std::cout << " is: " << best << "\nThe subarray starts at index: " << bestFrom << " and ends at index: " << bestTo << "\n\n";
	}
	else
	{
		*result = best;
		*from = bestFrom;
		*to = bestTo;
	}
}

void maximumSubmatrixSum(const Matrix<int>& values) // T(n) = O(n^3), M(n) = O(n^2)
{
	const size_t n = values.rows(), m = values.cols();
	Matrix<int> prefixes(n, m + 1, 0);
	for (size_t i = 0; i < n; i++)
	{
		prefixes[i][1] = values[i][0];
		for (size_t j = 2; j <= m; j++) prefixes[i][j] = prefixes[i][j - 1] + values[i][j - 1];
	}

	std::vector<int> temp;
	int best = values[0][0];
	size_t bestTop = 0, bestBottom = 0, bestLeft = 0, bestRight = 0;
	for (size_t left = 0; left < m; left++)
		for (size_t right = left; right < m; right++)
		{
			temp.clear();
			temp.resize(n, 0);
			for (int row = 0; row < n; row++)
				temp[row] = prefixes[row][right + 1] - prefixes[row][left];

			int current;
			size_t currTop, currBottom;
			maximumSubarraySum(temp, &current, &currTop, &currBottom);
			if (current > best)
			{
				best = current;
				bestTop = currTop;
				bestBottom = currBottom;
				bestLeft = left;
				bestRight = right;
			}
		}
	// return best;

	std::cout << values;
	std::cout << "The maximum submatrix sum is: " << best
			<< "\nwith top left corner at [" << bestTop << "][" << bestLeft
			<< "] and bottom right corner at [" << bestBottom << "][" << bestRight << "].\n\n";

}

int main()
{
	//minimumCoinCount({ 1,4,6 }, 8);
	//binomialCoefficient(5, 3);
	//longestIncreasingSubsequence({ 2,1,3,4,3,7,8,3,1,10 });
	//optimalSingleRobotPath({ {8,4,7,3}, {5,1,8,6}, {2,9,6,2} });
	//nDigitIntegerCount(3, 10);
	//Knapsack({ { 12,4 },{ 1,2 },{ 2,2 },{ 1,1 },{ 4,10 } }, 15);
	//KnapsackNoRepetitions({ { 12,4 },{ 1,2 },{ 2,2 },{ 1,1 },{ 4,10 } }, 15);
	//Partition({ 3,1,1,2,2,1 });
	//maximumSubarraySum({ -1,2,3,-2,4,-10,5,2,-3 });
	//maximumSubmatrixSum({ {1,2,-1,-4,-20},{-8,-3,4,2,1},{3,8,10,1,3},{-4,-1,1,7,-6} });
}