partition array for maximum sum

// Let k be 2
    // Focus on "growth" of the pattern
    // Define A' to be a partition over A that gives max sum
    
    // #0
    // A = {1}
    // A'= {1} => 1
    
    // #1
    // A = {1, 2}
    // A'= {1}{2} => 1 + 2 => 3 X
    // A'= {1, 2} => {2, 2} => 4 AC
        
    // #2
    // A = {1, 2, 9}
    // A'= {1, 2}{9} => {2, 2}{9} => 4 + 9 => 13 X
    // A'= {1}{2, 9} => {1}{9, 9} => 1 + 18 => 19 AC
    
    // #3
    // A = {1, 2, 9, 30}
    // A'= {1}{2, 9}{30} => {1}{9, 9}{30} => 19 + 30 => 49 X
    // A'= {1, 2}{9, 30} => {2, 2}{30, 30} => 4 + 60 => 64 AC
    
    // Now, label each instance. Use F1() to represent how A is partitioned and use F2() to represent
    // the AC value of that partition. F2() is the dp relation we are looking for.
    
    // #4
    // A = {1, 2, 9, 30, 5}
    // A'= F1(#3){5} => F2(#3) + 5 => 69 X
    // A'= F1(#2){30, 5} => F2(#2) + 30 + 30 => 79 AC
    // => F2(#4) = 79

Posted by: Guest on December-03-2020

Source

`` public int maxSumAfterPartitioning(int[] arr, int k) { /* if(i == n-1) return [n-1]; [],i,k int sum = 0; int max = -1; for(int j=i;j<i+k && j<n;j++){ max = max(max,[j]); int res = ([],j+1,k) sum = max(sum, max*(j-i+1) + res); } return sum; **/ int n = arr.length; int []dp = new int[n]; dp[n-1] = arr[n-1];//fill the base case //loop from behind because in above we need ans of j+1 // It can be done from front but I like this way its more intutive to me. for(int i=n-2;i>=0;i--){ int max = -1; int sum = 0; for(int j=i;j<i+k && j<n;j++){ max = Math.max(max,arr[j]); int sub = j<n-1?dp[j+1]:0;//get sub problem solution sum = Math.max(sum,max*(j-i+1)+ sub);//make current problem solution } dp[i] = sum;//fill current state } return dp[0]; }

Code answers related to "partition array for maximum sum"

Code answers related to "Whatever"

Browse Popular Code Answers by Language

Answers for "partition array for maximum sum"

Code answers related to "partition array for maximum sum"

Code answers related to "Whatever"

Browse Popular Code Answers by Language

Popular Programming Languages

Advertisements

Company

Compilers

Help

Connect with us