最大子数组

最大子数组(lintcode 41)

描述：给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
样例：给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6
要求时间复杂度为O(n)

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
   public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum = sum + nums[i];
            if(sum>max) max=sum;//注意顺序
            if(sum<0){
                sum = 0;
            }
            
        }
        return max;
    }
}

最大子数组 II（lincode42）

描述 ：给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。返回最大的和。

public class Solution {
    /*
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    public int maxTwoSubArrays(List<Integer> nums) {
        // write your code here
        int pre[]= new int[nums.size()];  
        int back[]=new int[nums.size()];
        int sum =0;
        int max = Integer.MIN_VALUE;
        for(int i=0;i<nums.size();i++){
            sum = sum + nums.get(i);
            if(sum>max) max = sum;
            if(sum<0) sum=0;
            pre[i] = max;
        }
        sum = 0;
        max = Integer.MIN_VALUE;
        for(int i=nums.size()-1;i>=0;i--){
            sum = sum + nums.get(i);
            if(sum>max) max = sum;
            if(sum<0) sum=0;
            back[i] = max;
        }
        max=Integer.MIN_VALUE;
        for(int i=0;i<nums.size()-1;i++){
            sum = pre[i]+back[i+1];
            if(sum>max) max = sum;
        }
        return max;
    }
}

买卖股票的最佳时机 III

描述：假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxTwoSubArrays(int nums[]) {
        // write your code here
        int pre[]= new int[nums.length];  
        int back[]=new int[nums.length];
        int sum =0;
        int max = Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            sum = sum + nums[i];
            if(sum>max) max = sum;
            if(sum<0) sum=0;
            pre[i] = max;
        }
        sum = 0;
        max = Integer.MIN_VALUE;
        for(int i=nums.length-1;i>=0;i--){
            sum = sum + nums[i];
            if(sum>max) max = sum;
            if(sum<0) sum=0;
            back[i] = max;
        }
        max=Integer.MIN_VALUE;
        for(int i=0;i<nums.length-1;i++){
            sum = pre[i]+back[i+1];
            if(sum>max) max = sum;
        }
        if(max<pre[nums.length-1]) max = pre[nums.length-1];//可以选择买一个
        if(max<0) max=0;//可以选择不买
        return max;
    }
    
     public int maxProfit(int[] prices) {
         if(prices.length<=1) return 0;
         int s[] = new int[prices.length-1];
         for(int i=1;i<prices.length;i++){
             s[i-1] = prices[i]-prices[i-1];
         }
         return maxTwoSubArrays(s);
     }
}

最接近零的子数组和（lintcode139）

描述：给定一个整数数组，找到一个和最接近于零的子数组。返回第一个和最右一个指数。你的代码应该返回满足要求的子数组的起始位置和结束位置

public class Main{
    class Pair{
        int val;
        int x;
        public Pair(int val,int x){
            this.val = val;
            this.x = x;
        }
    }
    public int[] subarraySumClosest(int[] nums) {
        int [] out = new int[2];
        Pair []s = new Pair[nums.length];
        int sum=0;
        for(int i=0;i<nums.length;i++){ 
            sum = sum + nums[i];
            Pair p = new Pair(sum,i);
            s[i] = p;
        }
        Arrays.sort(s,new Comparator<Pair>(){
            public int compare(Pair a, Pair b){
                return a.val-b.val;
            }
        });
        int min = Integer.MAX_VALUE;
        for(int i=1;i<nums.length;i++){
            int minor = s[i].val-s[i-1].val;
            if(minor<min){
                min = minor;
                //判断c[i],c[i-1]的大小，找到对应的分段
                if(s[i].x>s[i-1].x){
                    out[1] = s[i].x;
                    out[0] = s[i-1].x+1;
                }else{
                    out[0] = s[i].x+1;
                    out[1] = s[i-1].x;
                }
                
            }
        }
        System.out.println(out[0]+" "+out[1]);
        return out;
    }
    
    public static void main(String[] args)  {
        Main m = new Main();
        m.subarraySumClosest(new int[]{-3, 1, 1, -3, 5});
        //System.out.println(a);
    }
}