Descripción del problema: una matriz con n elementos, estos n elementos pueden ser positivos o negativos. Encuentra la suma de la subarrray más grande.
Método 1: Método de fuerza bruta
Idea: La forma más fácil y fácil de pensar es encontrar todos los subarrañas, luego encontrar la suma de todos los subarrays y obtener el valor máximo en la suma de todas las subarrays.
/ *** Método 1 (Método de fuerza bruta): Encuentre la suma de los subarrañas máximas en dos bucles*/ public static int maxsubarray1 (int [] a) {int i, j; int thisSum = 0; int maxsum = 0; para (i = 0; i <a.length; i ++) {thisSum = a [i]; para (j = i+1; j <a.length; j ++) {thisSum+= a [j]; if (thisSum> maxsum) {maxsum = thisSum; }} return maxSum; }Método 2: Programación dinámica optimizada
Idea: Primero, de acuerdo con la relación entre el último elemento A [N-1] de la matriz y la subarray más grande, se puede dividir en las siguientes tres situaciones:
1) La subarray máxima contiene una [N-1], es decir, que termina con un [N-1].
2) A [N-1] solo forma la subarrray más grande.
3) La subarray máxima no contiene un [N-1], por lo que encontrar la subarriny máxima de un [1, ..., N-1] puede convertirse para encontrar el subarrañamiento máximo de un [1, ..., n-2].
A través del análisis anterior, podemos sacar la siguiente conclusión: suponiendo que la suma de la matriz más grande de (a [0], ... a [i-1]) se haya calculado como todos [i-1], y la suma de la matriz más grande de a [i-1] en (a [0], ... a [i-1]) también se calcula como [i-1].
Entonces se puede obtener la siguiente relación: All [i-1] = max {a [i-1], final [i-1], todos [i-1]}. Use esta fórmula y la idea de la programación dinámica para resolver problemas. (El código también resuelve el problema de la posición inicial y la posición final)
/*** Método 2: Método de programación dinámica optimizada* La nend se obtiene agregando matrices a una [i] en secuencia, y luego comparándolas con un [i] ", y se guarda el más grande. Debido a public static int max (int m, int n) {return m> n? M: n; nend = max (nend+a [i], a [i]); maxsum = integer.min_value; int nstart = 0; for (int i = 0; i <a.length; i ++) {if (nsum <0) {nsum = a [i]; nStart = i; } else {nsum+= a [i]; } if (nsum> maxsum) {maxsum = nsum; begin = nstart; fin = i; }} return maxSum; }Lo anterior es todo el contenido de este artículo. Espero que el contenido de este artículo sea de ayuda para el estudio o el trabajo de todos. ¡También espero apoyar a Wulin.com más!