Computer Science, asked by rachana2621, 4 days ago

A family is about to break their piggy bank to use the money for different purposes. The piggy bank here represents an array (arr[]) consisting of N coins. The family has to split the coins of piggy bank into smaller stack (sub-array) of coins such that the sum of the difference between the maximum value and the minimum value of the coins for all the stacks (sub arrays) is maximum. Note: Each value of the array can be used only once that is only in one ons 60 array.
Constraints:
1<=N<=500
1<=arr[i]<=100

Answers

Answered by ayu06srivastava

Answer: 14

Explanation:

import java.util.Scanner;

import java.util.Arrays;

class maxSubarray{

public static void main(String[] args)

{

Scanner scan=new Scanner(System.in);

int n=scan.nextInt();

int a[]=new int[n];

for(int i=0;i<a.length;i++)

{

a[i]=scan.nextInt();

}

Arrays.sort(a);

int i=0;

int j=a.length-1;

int sum=0;

while(i<j)

{

int dif=(a[j]-a[i]);

sum=sum+dif;

i++;

j--;

}

System.out.print(sum);

}

Answered by surajnegi0600

Answer:

The given problem can be solved using a Dynamic Programming approach. We can use a two-dimensional array dp[i][j] where i indicates the starting index and j indicates the ending index of the coins in the piggy bank. Each element of this array is the maximum sum of the difference between the maximum and the minimum coins in the given subarray.

Explanation:

We can recursively calculate the value of dp[i][j] as follows:

dp[i][j] = max(dp[i][j-1], max(arr[j] - arr[k]+ dp[i][k-1]))

where i < k < j

Here, dp[i][j-1] corresponds to the case when the last coin is not included in the subarray and max(arr[j] - arr[k]+ dp[i][k-1]) corresponds to the case when the last coin is included in the subarray. The maximum of these two cases is taken to find the value of dp[i][j].

The base case of this recurrence relation is dp[i][i] = 0.

Once we have this two-dimensional array, the required answer would be the maximum value in the array. The overall time complexity of this solution is O(n2).