|
| 1 | +packagecom.fishercoder.solutions; |
| 2 | + |
| 3 | +publicclass_1690 { |
| 4 | +publicstaticclassSolution1 { |
| 5 | + |
| 6 | +int[]stonesRef; |
| 7 | + |
| 8 | +int[]prepareSums; |
| 9 | + |
| 10 | +int[][]maxDiffScoureBetweenTowPlayerWhenPlayInPosItoJ =newint[1005][1005]; |
| 11 | + |
| 12 | +publicintstoneGameVII(int[]stones) { |
| 13 | +this.stonesRef =stones; |
| 14 | +inttotalStonesNumber =stones.length; |
| 15 | +this.prepareSums =newint[totalStonesNumber +1]; |
| 16 | +for (inti =1;i <=totalStonesNumber;i++) { |
| 17 | +this.prepareSums[i] =this.prepareSums[i -1] +stones[i -1]; |
| 18 | + } |
| 19 | +for (intlen =1;len <=totalStonesNumber;len++) { |
| 20 | +for (inti =1;i +len -1 <=totalStonesNumber;i++) { |
| 21 | +intj =i +len -1; |
| 22 | +this.setMaxDiffScoureBetweenTowPlayerWhenPlayInPosItoJ(i,j); |
| 23 | + } |
| 24 | + } |
| 25 | +returnmaxDiffScoureBetweenTowPlayerWhenPlayInPosItoJ[1][totalStonesNumber]; |
| 26 | + } |
| 27 | + |
| 28 | +privatevoidsetMaxDiffScoureBetweenTowPlayerWhenPlayInPosItoJ(inti,intj) { |
| 29 | +if (j -i ==0) { |
| 30 | +maxDiffScoureBetweenTowPlayerWhenPlayInPosItoJ[i][j] =0; |
| 31 | + }elseif (j -i ==1) { |
| 32 | +maxDiffScoureBetweenTowPlayerWhenPlayInPosItoJ[i][j] =Math.max(stonesRef[i -1],stonesRef[j -1]); |
| 33 | + }else { |
| 34 | +maxDiffScoureBetweenTowPlayerWhenPlayInPosItoJ[i][j] =Math.max( |
| 35 | +this.sumOfTheStonesValueInPosIToJ(i +1,j) |
| 36 | + -maxDiffScoureBetweenTowPlayerWhenPlayInPosItoJ[i +1][j], |
| 37 | +this.sumOfTheStonesValueInPosIToJ(i,j -1) |
| 38 | + -maxDiffScoureBetweenTowPlayerWhenPlayInPosItoJ[i][j -1]); |
| 39 | + } |
| 40 | + } |
| 41 | + |
| 42 | +privateintsumOfTheStonesValueInPosIToJ(inti,intj) { |
| 43 | +returnthis.prepareSums[j] -this.prepareSums[i -1]; |
| 44 | + } |
| 45 | + } |
| 46 | +} |