Best Partition

You are given an array of positive numbers of size $N$ and an integer K$.$ You need to partition the array into K

continuous segments. For each segment, the sum of its elements needs to be calculated.

The segment with the minimum sum is called the bestSegment and the sum of the elements of the

bestSegment is called the bestSum.

For all possible combinations of partitions of the array when divided into K segments, their bestSum needs to be

calculated and the one among them with maximum value needs to be returned.

My stuff $,$ Input Specification:

input$1$: an array of $N$ positive numbers

input$2$: an integer $N$ denoting the length of the array

input$3$: an integer $K$

Output Specification:

Return an integer denoting the maximum value of all possible bestSum.

Example $1$:

input $1$: $\{1,2,3,4\}$

input$2$: $4$

input$3$: $2$

Output : $4$

Explanation:

You can partition the given array into $2$ continuous segments in the following manner$-$input$3$: $2$

Output : $4$

Explanation:

You can partition the given array into $2$ continuous segments in the following manner$-$

$123|4-$ the sum of individual segments is $\{6,4\}$ and the bestSum is $4$

$12|34-$ the sum of individual segments is $\{3,7\}$ and the bestSum is $3$

$1|234-$ the sum of individual segments is $\{1,9\}$ and the bestSum is $1$

The maximum value of bestSum among $\{4,3,1\}$ is $4.$ So$,4$ will be returned as the answer.

Example $2$:

input $1$:$\{5,6,6,8\}$

input$2$: $4$

input$3$: $4$

Output : $5$

Explanation:

You can partition the given array into $4$ continuous segments only in one way$-$

$5|6|6|8-$ The sum of individual segments is $\{5,6,6,8\}$ and the bestSum is $5.$

Since the only value of bestSum is $5,$ it will be returned as the answer. Previously I have contacted expert in Chegg. He provided this code public class MaxBestSum $\{$

public static int maxBestSum$($int$[]$ arr, int N$,$ int K$)\{$

if $($arr $==$ null $||$ N $==0||$ K $<=0||$ K $>$ N$)\{$

return $0$; $//$ Invalid input

$\}$

int$[][]$ dp $=$ new int$[$K $+1][$N $+1]$;

for $($int k $=1$; k $<=$ K; k$++)\{$

for $($int n $=$ k; n $<=$ N; n$++)\{$

int currentSum $=0$;

int bestSum $=$ Integer.MAX$\_$VALUE;

for $($int i $=$ n; i $>=$ k; i$--)\{$

currentSum $+=$ arr$[$i $-1]$;

bestSum $=$ Math.min$($bestSum$,$ Math.max$($dp$[$k $-1][$i $-1],$ currentSum$))$;

$\}$

dp$[$k$][$n$]=$ bestSum;

$\}$

$\}$

return dp$[$K$][$N$]$;

$\}$

public static void main$($String$[]$ args$)\{$

int$[]$ inputArray $=\{1,2,3,4\}$;

int N $=4$;

int K $=2$;

int result $=$ maxBestSum$($inputArray$,$ N$,$ K$)$;

System.out.println$("$Maximum bestSum: $"+$ result$)$;

$\}$

$\}$But this code doesn't works for $2$nd example please rectify the error in this code and provide me in Java