Нахождение подпоследовательности максимального веса массива натуральных чисел?
Попробуйте это в Java: это даст вам длинную версию строки (UTF-8)
byte[] encoded = Base64.encode(encrypted.getBytes("UTF-8"), Base64.DEFAULT);
String str = new String(encoded, "UTF-8");
Обновлено:
Попробуйте это на Java: это даст вы короткая версия строки (CP1252)
// This should give the same results as in PHP
byte[] encoded = Base64.encode(encrypted.getBytes("CP1252"), Base64.DEFAULT);
String str = new String(encoded, "CP1252");
Альтернативно попробуйте этот скрипт PHP:
file: test.php
<?php
echo base64_encode($_GET['str'])." Default UTF-8 version<br />";
echo base64_encode(iconv("UTF-8","CP1252",$_GET['str']))." CP1252 Version <br />";
?>
usage: http://[SOMEDOMAIN]/test.php?str=†+Ü]M(‡=ñö
2 ответа
Я действительно не понимаю этот псевдокод, поэтому опубликуйте код C ++, если он не помогает, и я постараюсь его улучшить.
Я пытаюсь найти подпоследовательность с максимальным весом для массива положительных целых чисел - загвоздка в том, что в последней подпоследовательности не разрешены никакие соседние элементы.
Пусть a будет вашим массивом положительных целых чисел. Пусть f [i] = значение подпоследовательности с максимальным весом последовательности a [0..i] .
У нас есть:
f [0] = a [0] , потому что, если есть только один элемент, мы должны его взять.
f [1] = max (a [0], a [1]) , потому что у вас нет ограничения на соседние элементы, поэтому, если у вас есть два элемента, вы можете взять только один из них. Имеет смысл брать самый крупный.
Обычно у вас есть:
f[i > 1] = max(
f[i - 2] + a[i] <= add a[i] to the largest subsequence of the sequence a[0..i - 2]. We cannot take a[0..i - 1] because otherwise we risk adding an adjacent element.
f[i - 1] <= don't add the current element to the maximum of a[0..i - 2], instead take the maximum of a[0..i - 1], to which we cannot add a[i].
)
Я думаю, что этот способ легче понять, чем то, что у вас там есть. Подходы эквивалентны, я просто нахожу это более ясным для этой конкретной проблемы, поскольку в этом случае рекурсия усложняет задачу, и псевдокод в любом случае может быть более ясным.
Но чего вы НЕ понимаете? Для меня это кажется совершенно ясным:
- мы построим максимальную подпоследовательность для каждого префикса нашей данной последовательности
- , чтобы вычислить максимальную подпоследовательность для префикса длины
i, мы рассмотрим две возможности: Либо последний элемент входит или не входит в максимальную подпоследовательность (очевидно, что других возможностей нет). - если он есть, мы рассматриваем значение последнего элемента плюс значение максимальной подпоследовательности префикса на два элемента короче (потому что в этом случае мы знаем, что последний элемент не может присутствовать в максимальной подпоследовательности из-за правило смежных элементов )
- если это не так, мы берем значение максимальной суммы префикса на один элемент короче (если последний элемент префикса не входит в максимальную подпоследовательность, максимальная подпоследовательность должна быть быть равным для этого и предыдущего префикса)
- мы сравниваем и берем максимум из двух
Плюс: вам нужно запомнить фактические подпоследовательности; вам нужно избегать излишних вызовов функций, отсюда и мемоизация.
Почему он расширяет
f []до[], 0?
Потому что первое из пары в возвращаемом значении означает текущую максимальную подпоследовательность, а второе - ее значение. Максимальная подпоследовательность пустой последовательности пуста и имеет нулевое значение.