九度OJ 1527 首尾相连数组的最大子数组和 -- 动态规划 - c++编程基础

题目描述：

给定一个由N个整数元素组成的数组arr，数组中有正数也有负数，这个数组不是一般的数组，其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组，其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j]，现在请你这个ACM_Lover用一个最高效的方法帮忙找出所有连续子数组和的最大值（如果数组中的元素全部为负数，则最大和为0，即一个也没有选）。

输入：

输入包含多个测试用例，每个测试用例共有两行，第一行是一个整数n（1= 输出：

对于每个测试用例，请输出子数组和的最大值。

样例输入：

6
1 -2 3 5 -1 2
5
6 -1 5 4 -7

样例输出：

10
14

来源：

淘宝2013年校园招聘一面面试题

#include 
    
     
 
int Max_Sub (int arr[], int n){
    int i;
    int tmp;
    int max;
 
    tmp = max = arr[0];
    for (i=1; i
     
       0) tmp += arr[i]; else tmp = arr[i]; if (tmp > max) max = tmp; } return max; } int Max_Left (int arr[], int n, int * left){ int i; int tmp; int max; tmp = max = arr[0]; *left = 0; for (i=1; i
      
        max){ max = tmp; *left = i; } } return max; } int Max_Right (int arr[], int n, int * right){ int i; int tmp; int max; tmp = max = arr[n-1]; *right = 0; for (i=n-2; i>=0; --i){ tmp += arr[i]; if (tmp > max){ max = tmp; *right = i; } } return max; } int Min_Sub (int arr[], int n){ int i; int tmp; int min; tmp = min = arr[0]; for (i=1; i
       
         0) flag = 1; } if (flag == 1){ max = Max_Sub (arr, n); left_max = Max_Left (arr, n, &left); right_max = Max_Right (arr, n, &right); if (left > right){ mmax = 0; for (i=0; i
        
          mmax)   max : mmax); } else printf (0 ); } return 0; } /************************************************************** Problem: 1527 User: 简简单单Plus Language: C Result: Accepted Time:80 ms Memory:1232 kb ****************************************************************/