Descrição do problema: uma matriz com n elementos, esses n elementos podem ser positivos ou negativos. Encontre a soma do maior subarray.
Método 1: método de força bruta
Ideia: A maneira mais fácil e fácil de pensar é encontrar todos os subarrays, encontrar a soma de todos os subarrays e obter o valor máximo na soma de todos os subarraias.
/ *** Método 1 (método de força bruta): Encontre a soma dos subarraias máximas em dois loops*/ public static int maxsubarray1 (int [] a) {int i, j; int thisSum = 0; int maxsum = 0; for (i = 0; i <A.Length; i ++) {thisSum = a [i]; for (j = i+1; j <A.Length; j ++) {thissum+= a [j]; if (thissum> maxsum) {maxsum = thissum; }} retornar maxsum; }Método 2: Programação dinâmica otimizada
Ideia: Primeiro, de acordo com a relação entre o último elemento A [n-1] da matriz e o maior subarray, pode ser dividido nas três situações a seguir:
1) O subarray máximo contém um [N-1], ou seja, terminando com um [N-1].
2) Somente um [N-1] forma o maior subarray.
3) O subarray máximo não contém um [N-1]; portanto, encontrar o subarray máximo de A [1, ..., N-1] pode ser convertido para encontrar o subarray máximo de A [1, ..., N-2].
Através da análise acima, podemos tirar a seguinte conclusão: assumindo que a soma da maior variedade de (a [0], ... a [i-1]) foi calculada como todos [i-1], e a soma da maior matriz de um [i-1] em (a [0], ... a [i-1]) também é calculada como final [i-1].
Em seguida, o seguinte relacionamento pode ser obtido: todos [i-1] = max {a [i-1], end [i-1], todos [i-1]}. Use esta fórmula e a idéia de programação dinâmica para resolver problemas. (O código também resolve o problema da posição inicial e da posição final)
/*** Método 2: O método de programação dinâmica otimizado* é obtido adicionando matrizes a um [i] em sequência e depois comparando -os com um [i] ", e salvou o maior. Porque se o número anterior não é adicionado a uma maior contribuição e a maior sub -que a Subarray. 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; fim = i; }} retornar maxsum; }O exposto acima é todo o conteúdo deste artigo. Espero que o conteúdo deste artigo seja de ajuda para estudar ou trabalhar de todos. Eu também espero apoiar mais wulin.com!