Knapsack 01
#CPP
#include <iostream>
#include <vector>

using std::vector;
using std::max;

int knapsack_01(vector<int> profit, vector<int> weight, int capacity) {
int n = 2, m = capacity, counter = 0, skip, include;
vector<vector<int>> dp(2);

dp[0] = vector<int>(m + 1);
dp[1] = vector<int>(m + 1);

counter = 0;
while (counter <= m) {
if (weight[0] <= counter)
dp[0][counter] = profit[0];

counter++;
}

counter = 1;
while (counter < profit.size()) {
for (int i = 0; i < m + 1; i++) {
skip = dp[1][i];
include = 0;
if (i - weight[counter] >= 0)
include = profit[counter] + dp[0][i - weight[counter]];
dp[1][i] = max(include, skip);
}

dp[0] = dp[1];
counter++;
}

return dp[1][m];
}


int main() {

vector<int> profit{ 4, 4, 7, 1, 8, 9 }, weight{5, 2, 3, 1, 4, 5};
int capacity = 8, result;

result = knapsack_01(profit, weight, capacity);


}
Knapsack 0/1 Dynamic Programming
#CPP
#include <iostream>
#include <vector>

using std::vector;
using std::max;

int knapsack_01(vector<int> profit, vector<int> weight, int capacity) {
int n = 2, m = capacity, counter = 0, skip, include;
vector<vector<int>> dp(2);

dp[0] = vector<int>(m + 1);
dp[1] = vector<int>(m + 1);

counter = 0;
while (counter <= m) {
if (weight[0] <= counter)
dp[0][counter] = profit[0];

counter++;
}

counter = 1;
while (counter < profit.size()) {
for (int i = 0; i < m + 1; i++) {
skip = dp[1][i];
include = 0;
if (i - weight[counter] >= 0)
include = profit[counter] + dp[0][i - weight[counter]];
dp[1][i] = max(include, skip);
}

dp[0] = dp[1];
counter++;
}

return dp[1][m];
}


int unbounded_knapsack_01(vector<int> profit, vector<int> weight, int capacity) {
int N = profit.size(), M = capacity, counter = 0, skip = 0, include = 0;
vector<int> dp(M + 1), currRow(M+1);

for (counter = 0; counter < N; counter++) {
currRow = vector<int>(M + 1);

for (int i = 1; i <= M; i++) {
skip = dp[i];
include = 0;
if (i - weight[counter] >= 0) {
include = profit[counter] + currRow[i - weight[counter]];
}
currRow[i] = max(include, skip);
}
dp = currRow;
}
return dp[M];
}

int main() {

vector<int> profit{ 4, 4, 7, 1 }, weight{5, 2, 3, 1, 4, 5};
int capacity = 8, result;

result = knapsack_01(profit, weight, capacity);

result = unbounded_knapsack_01(profit, weight, capacity);

}
Longest common subsequece
#CPP
#include <iostream>
#include <vector>

using std::vector;
using std::string;
using std::max;

// Longest common subsequence (LCS)

int lcs_helper(string s1, string s2, int c1, int c2) {
if (c1 == s1.size() || c2 == s2.size())
return 0;

if (s1[c1] == s2[c2])
return 1 + lcs_helper(s1, s2, c1 + 1, c2 + 1);
else
return max(lcs_helper(s1, s2, c1 + 1, c2), lcs_helper(s1, s2, c1, c2 + 1));
}

static int lcs(string s1, string s2) {
return lcs_helper(s1, s2, 0, 0);
}


int memoized_lcs_helper(string s1, string s2, int c1, int c2, vector<vector<int>> cache) {
if (c1 == s1.size() || c2 == s2.size())
return 0;

if (cache[c1][c2] != -1)
return cache[c1][c2];

if (s1[c1] == s2[c2])
cache[c1][c2] = 1 + memoized_lcs_helper(s1, s2, c1 + 1, c2 + 1, cache);
else
cache[c1][c2] = max(memoized_lcs_helper(s1, s2, c1 + 1, c2, cache), memoized_lcs_helper(s1, s2, c1, c2 + 1, cache));
return cache[c1][c2];
}

int memoized_lcs(string s1, string s2) {
int N = s1.size(), M = s2.size(), result;
vector<vector<int>> cache(N, vector<int>(M, -1));

result = memoized_lcs_helper(s1, s2, 0, 0, cache);
return result;
}

int lcs_dp(string s1, string s2) {
size_t N = s1.size(), M = s2.size(), cnt1, cnt2;
vector<vector<int>> dp(N + 1, vector<int>(M+1, 0));

for (cnt1 = 0; cnt1 < N; cnt1++)
for (cnt2 = 0; cnt2 < M; cnt2++)
if (s1[cnt1] == s2[cnt2])
dp[cnt1 + 1][cnt2 + 1] = 1 + dp[cnt1][cnt2];
else
dp[cnt1 + 1][cnt2 + 1] = max(dp[cnt1][cnt2 + 1], dp[cnt1 + 1][cnt2]);
return dp[N][M];
}

int optimized_lcs_dp(string s1, string s2) {
size_t N = s1.size(), M = s2.size(), cnt1, cnt2;
vector<int> dp(M + 1, 0), curRow;

for (cnt1 = 0; cnt1 < N; cnt1++) {
curRow = vector<int>(M+1, 0);
for (cnt2 = 0; cnt2 < M; cnt2++)
if (s1[cnt1] == s2[cnt2])
curRow[cnt2 + 1] = 1 + dp[cnt2];
else
curRow[cnt2 + 1] = max(dp[cnt2 + 1], curRow[cnt2]);
dp = curRow;
}
return curRow[M];
}


int main() {
int result = lcs("ADCB", "ABC");
result = memoized_lcs("ADCB", "ABC");
result = lcs_dp("ADCB", "ABC");
result = optimized_lcs_dp("ADCB", "ABC");

}
Longest Palindrome
#CPP cp
#include <algorithm>
#include <vector>
#include <ranges>

using std::vector;
using std::string;
using std::max;

// palindromes
static int longest_palindrome(string s) {
int length = 0, size = s.size(), left, right;

for (int counter = 0; counter < size; counter++) {

// odd length
left = right = counter;
while (left >= 0 && right < size && s[left] == s[right]) {
if ((right - left + 1) > length) {
length = right - left + 1;
}
left--;
right++;
}

// even length
left = counter;
right = counter + 1;
while (left >= 0 && right < size && s[left] == s[right]) {
if ((right - left + 1) > length) {
length = right - left + 1;
}
left--;
right++;
}
}
return length;
}

int main() {
int result;

result = longest_palindrome("abaazbaabadfsddsfd");

}
#AlgoExpert
#TwoNumberSum
#include <vector>
#include <algorithm>

using std::vector;
using std::count;
using std::pair;

pair<int, int> TwoNumberSum(vector<int> lst, int targetSum) {
int left = 0, right = lst.size() - 1, curSum;

std::ranges::sort(lst);
while (left < right) {
curSum = lst[left] + lst[right];
if (curSum == targetSum)
return { lst[left], lst[right] };
else if (curSum < targetSum)
left++;
else
right--;
}
return {};
}


int main()
{
vector<int> v{ -4, -1, 1, 3, 5, 6, 8, 11 };

auto result = TwoNumberSum(v, 60);


}
#AlgoExpert
#ValidateSubsequence
#include <algorithm>
#include <vector>

using std::vector;

// validate subsequence
bool validateSubsequence(vector<int> lst, vector<int> subsequence) {
int lst_counter = 0, subs_counter = 0;
while(lst_counter < lst.size() && subs_counter < subsequence.size()){
if (lst[lst_counter] == subsequence[subs_counter])
subs_counter++;
lst_counter++;
}

return subs_counter == subsequence.size();
}

int main()
{
vector<int> lst{ 5, 1, 22, 25, 6, -1, 8, 10 }, subs{1, 6, -1, 10};

bool result = validateSubsequence(lst, subs);

return 0;
}
#AlgoExpert
#SortedSquaredArray
#include <algorithm>
#include <ranges>
#include <vector>

using std::vector;

// sorted squared array
static vector<int> sortedSqArr(vector<int> lst) {
int N = lst.size(), start = 0, end = lst.size() - 1, i; // setup pointers
vector<int> result(N);

i = end;
while (i >= 0) {
if (abs(lst[start]) <= abs(lst[end])) {
result[i] = lst[end] * lst[end];
end--;
}
else if (abs(lst[start]) > abs(lst[end])) {
result[i] = lst[start] * lst[start];
start++;
}
i--;
}
return result;
}


int main() {
vector<int> lst{ -7, -5, -4, 3, 6, 8, 9 };
auto result = sortedSqArr(lst);

return 0;
}
#TwoNumberSum Challenge
Challenge Description:
Your task is to write a function that takes in an array of integers and a target sum. The function should find and return a pair of distinct numbers in the array that add up to the target sum. If no such pair is found, the function should return an empty array.

چالش #TwoNumberSum
توضیحات چالش:
وظیفه شما این است که یک تابع بنویسید که یک آرایه از اعداد صحیح و یک جمع هدف را به عنوان ورودی بگیرد. تابع باید یک زوج از اعداد متمایز در آرایه را پیدا کند و برابر با جمع هدف باشد. اگر چنین زوجی پیدا نشود، تابع باید یک آرایه خالی برگرداند.
CP - Algorithms pinned «#TwoNumberSum Challenge Challenge Description: Your task is to write a function that takes in an array of integers and a target sum. The function should find and return a pair of distinct numbers in the array that add up to the target sum. If no such pair…»
#AlgoExpert
#TournamentWinner
#include <algorithm>
#include <ranges>
#include <map>
#include <vector>

using std::map;
using std::vector;
using std::string;
using std::ranges::for_each;
using std::pair;

// TournamentWinner
static pair<string, int> tournament_winner(vector<vector<string>> competitions, vector<int> results) {
map<string, int> scores; int index = 0;
pair<string, int> max{}, cur;

for_each(results, [&](int result) {
if (result == 0) {
scores[competitions[index][1]] += 3;
cur = { competitions[index][1], scores[competitions[index][1]] };
}
else if (result == 1) {
scores[competitions[index][0]] += 3;
cur = { competitions[index][0], scores[competitions[index][0]] };
}
index++;
if (cur.second > max.second)
max = cur;
});

return max;
}

int main() {
auto result = tournament_winner({ {"HTML", "C#"}, {"C#", "Python"}, {"Python", "HTML"} }, { 0, 0, 1 });

return 0;
}
#AlgoExpert
#NonConstructibleChange
#include <algorithm>
#include <vector>

using std::vector;
using std::ranges::sort;
using std::ranges::for_each;

// nonConstructibleChange() -> int
static int non_constructible_change(vector<int> coins) {
int change = 0;
sort(coins);

for_each(coins, [&](int coin) {
if (coin > change + 1)
return change + 1;
else
change += coin;
});

return change + 1;
}

int main() {
auto result = non_constructible_change({5, 7, 1, 1, 2, 3, 21});

return 0;
}