Minimum Subarray

Description

Given an array of integers, find the subarray with smallest sum.
Return the sum of the subarray.

Notice
The subarray should contain one integer at least.

Example
For [1, -1, -2, 1], return -3.

Link

Lintcode_ladder

Method

1. local[current] record whether current num can be selected
   keep tracking the
   min(current num, local[last] + current num) global[current] record minimum sum
   keep tracking
   min(global[last], local[current])
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param nums: a list of integers
     * @return: A integer denote the sum of minimum subarray
     */
    int minSubArray(vector<int> nums) {
        // write your code here
        if (nums.empty()) {
            return 0;
        }
        int len = nums.size();
        vector<int> local(len, INT_MAX);
        vector<int> global(len, INT_MAX);
        // init
        local[0] = nums[0];
        global[0] = nums[0];
        // @param local : current possible min seq
        // @param global : if prev min is minimum, it will continue
        for (int i = 1; i < len; ++i) {
            local[i] = min(nums[i], local[i-1] + nums[i]);
            global[i] = min(global[i-1], local[i]);
        }
        // for (int i = 0; i < local.size(); ++i) {
        //     cout << local[i] << " ";
        // }
        // cout << endl << "---------" << endl;
        // for (int i = 0; i < global.size(); ++i) {
        //     cout << global[i] << " ";
        // }
        // cout << endl << "---------" << endl; 
        return global[len-1];
    }
};

Similar problems

x

Tags

x