Competitive_Programming/LeetCode/Company_Questions/Google/Split_Array_Largest_Sum.cpp at master · Ravi-Maurya/Competitive_Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int n=nums.size();
        vector<long long> sua(nums.size()+1);
        sua[n-1]=nums[n-1];
        for(int i=n-2;i>=0;i--){
            sua[i]=nums[i]+sua[i+1];
        }
        vector<vector<long long > > dp(n+1,vector<long long >(m+1,-1));
        for(int i=1;i<=m;i++){
            dp[n-1][i]=nums[n-1];
        }
        for(int i=1;i<=m;i++){
            dp[n][i]=INT_MAX;
        }
        for(int i=0;i<n;i++){
            dp[i][1]=sua[i];
        }
        for(int i=n-2;i>=0;i--){
            for(int k=2;k<=m;k++){
                long long ma=INT_MAX,su=0;
                for(int j=i;j<n;j++){
                    su+=nums[j];
                    ma=min(ma,max(su,dp[j+1][k-1]));
                }
                dp[i][k]=ma;
            }
        }
        return dp[0][m];
    }
};

// My Approach use memoization
// class Solution {
// public:
//     int recursive(vector<int>& nums, int m, int n){
//         if(n<0)
//             return INT_MAX;
//         if(m==1){
//             int sum = 0;
//             for(int i=n;i>=0;i--)
//                 sum += nums[i];
//             return sum;
//         }
//         int sum = 0;
//         int res = INT_MAX;
//         for(int i = n; i>=0; i--){
//             sum += nums[i];
//             res = min(res,max(sum,recursive(nums,m-1,i-1)));
//         }
//         return res;
//     }
//     int splitArray(vector<int>& nums, int m) {
//         return recursive(nums,m,nums.size()-1);
//     }
// };