Find maximum sum array of length less than or equal to m | C # program to find maximum sum of array of size less than or equal to m from given n arrays ; N and M to define sizes of arr , dp , current_arr and maxSum ; INF to define min value ; Function to find maximum sum ; dp array of size N x M ; current_arr of size M ; maxsum of size M ; if we have 0 elements from 0 th array ; compute the cumulative sum array ; calculating the maximum contiguous array for every length j , j is from 1 to lengtn of the array ; every state is depending on its previous state ; computation of dp table similar approach as knapsack problem ; now we have done processing with the last array lets find out what is the maximum sum possible ; Driver Code ; first element of each row is the size of that row
using System ; class GFG { static int N = 105 ; static int M = 1001 ; static int INF = - 1111111111 ; static int maxSum ( int [ ] [ ] arr ) { int [ , ] dp = new int [ N , M ] ; int [ ] current_arr = new int [ M ] ; int [ ] maxsum = new int [ M ] ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) dp [ i , j ] = - 1 ; } current_arr [ 0 ] = 0 ; dp [ 0 , 0 ] = 0 ; for ( int i = 1 ; i <= 5 ; i ++ ) { int len = arr [ i - 1 ] [ 0 ] ; for ( int j = 1 ; j <= len ; j ++ ) { current_arr [ j ] = arr [ i - 1 ] [ j ] ; current_arr [ j ] += current_arr [ j - 1 ] ; maxsum [ j ] = INF ; } for ( int j = 1 ; j <= len && j <= 6 ; j ++ ) for ( int k = 1 ; k <= len ; k ++ ) if ( j + k - 1 <= len ) maxsum [ j ] = Math . Max ( maxsum [ j ] , current_arr [ j + k - 1 ] - current_arr [ k - 1 ] ) ; for ( int j = 0 ; j <= 6 ; j ++ ) dp [ i , j ] = dp [ i - 1 , j ] ; for ( int j = 1 ; j <= 6 ; j ++ ) for ( int cur = 1 ; cur <= j && cur <= len ; cur ++ ) dp [ i , j ] = Math . Max ( dp [ i , j ] , dp [ i - 1 , j - cur ] + maxsum [ cur ] ) ; } int ans = 0 ; for ( int i = 0 ; i <= 6 ; i ++ ) ans = Math . Max ( ans , dp [ 5 , i ] ) ; return ans ; } static void Main ( ) { int [ ] [ ] arr = new int [ ] [ ] { new int [ ] { 3 , 2 , 3 , 5 } , new int [ ] { 2 , 7 , - 1 } , new int [ ] { 2 , 8 , 10 } , new int [ ] { 4 , 5 , 2 , 6 , 1 } , new int [ ] { 3 , 2 , 3 , - 2 } } ; Console . Write ( " Maximum ▁ sum ▁ can ▁ be ▁ " + " obtained ▁ is ▁ : ▁ " + maxSum ( arr ) + " STRNEWLINE " ) ; } }