Split Array Largest Sum

Problem Description

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.

Return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

Intuition

The front element of preorder traversal determines the tree’s root node(the middle of inorder traversal). We use it to determine which element belong to the left subtree or right subtree, and keep comparing the preorder and inorder traversals. This way, we can construct the entire tree from these two traversals.

Algorithm

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
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < preorder.size(); i++){
        }
        return build(preorder, inorder, 0, preorder.size(), 0, inorder.size());
    }

    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pre_start, int pre_end, int in_start, int in_end){

        if(pre_start >= pre_end){
            return NULL;
        }
        TreeNode* root = new TreeNode(preorder[pre_start]);

        int split_point = -1;
        for(int i = in_start; i < in_end; i++){
            if(inorder[i] == preorder[pre_start]){
                split_point = i;
                break;
            }
        }

        int left_size = split_point - in_start;

        root->left = build(preorder, inorder, 
                           pre_start + 1, pre_start + 1 + left_size, 
                           in_start, split_point);
        root->right = build(preorder, inorder, 
                            pre_start + 1 + left_size, pre_end, 
                            split_point + 1, in_end);

        return root;
    }
};