Find maximum sum array of length less than or equal to m | A Dynamic Programming based 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 program ; first element of each row is the size of that row
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  105  NEW_LINE #define M  1001  NEW_LINE #define INF  -1111111111  NEW_LINE int maxSum ( int arr [ ] [ N ] ) { int dp [ N ] [ M ] ; int current_arr [ M ] ; int maxsum [ M ] ; memset ( dp , -1 , sizeof ( dp [ 0 ] [ 0 ] ) * N * M ) ; 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 ] = 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 ] = max ( dp [ i ] [ j ] , dp [ i - 1 ] [ j - cur ] + maxsum [ cur ] ) ; } int ans = 0 ; for ( int i = 0 ; i <= 6 ; i ++ ) ans = max ( ans , dp [ 5 ] [ i ] ) ; return ans ; } int main ( ) { int arr [ ] [ N ] = { { 3 , 2 , 3 , 5 } , { 2 , 7 , -1 } , { 2 , 8 , 10 } , { 4 , 5 , 2 , 6 , 1 } , { 3 , 2 , 3 , -2 } } ; cout << " Maximum ▁ sum ▁ can ▁ be ▁ obtained ▁ " << " is ▁ : ▁ " << maxSum ( arr ) << " STRNEWLINE " ; }