Algoritmos

PARTICIPACION EN FORO - SEMANA 5 Y 6

Se anexa proyecto (NetBeans) para su revisión:


DETALLE

PROBLEMA 1:
“Dada una secuencia de n enteros, se desea encontrar el máximo valor que se puede obtenersumando elementos consecutivos. Por ejemplo, para la secuencia (5, -3, 2, 8, -5, 2, 1), este valor es 12, que se obtiene de la subsecuencia (5, -3, 2, 8). Si una secuencia tiene todos númerosnegativos, se entiende que su subsecuencia de suma máxima es la vacía, por lo tanto el valor es 0. La idea es dar una solución a este ejercicio con complejidad O(n^2) y otra con complejidad O(n*log n), o darideas para solucionarlo. Además, decir la complejidad del algoritmo con análisis de complejidad o dar ideas para hacerlo.”
Solución propuesta: Complejidad O(n^2)
//Complejidad O(n^2)
//packagemaxsumsubsq;
import java.util.Scanner;
public class MaxSumSubsq {
public static void main(String[] args) {
int n;
Scanner scan = new Scanner(System.in);
int a[] = {5, -3, 2, 8,-5, 2, 1};
n = a.length;
int sum[] = new int[n];
sum[0] = a[0];
for (int i = 1; i < n; i++) {
sum[i] = sum[i - 1] + a[i];
}
int max =0;
int dif;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
dif = sum[j] - sum[i];
if (dif > max) {
max =dif;
}
}
if (sum[i] > max) {
max = sum[i];
}
}
System.out.println(max);
}
}


Solución propuesta: ComplejidadO(n*log n)

package maxsumsubsq;
public class MaxSumNlogN {
public static Subseq dividirVencer(int[] a) {
return busqueda(a, 0, a.length - 1);
}
private static Subseq busqueda(int[] a,int prim, int ult) {
if (ult - prim + 1 <= 7) {
return busquedaCuadrática(a, prim, ult);
}
int mitad = (ult + prim) / 2;
Subseq sIzq = busqueda(a, prim,...